oj.uz

답안 #243585

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
243585 2020-07-01T11:08:10 Z Dremix10 삶의 질 (IOI10_quality) C++17
60 / 100
 5000 ms 20856 KB 
#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
//#define endl '\n'
#define p(x) cerr<<#x<<" = "<<x<<endl;
#define p2(x,y) cerr<<#x<<" , "<<#y<<" = "<<x<<" , "<<y<<endl;
#define pp(x) cerr<<#x<<" = ("<<x.F<<" , "<<x.S<<")"<<endl;
#define pv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u<<", ";cerr<<"}"<<endl;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define maxp 22
#define EPS (ld)(1e-18)
#define mod (int)(1e9+7)
#define N (int)(1e5+1)

int rectangle(int n, int m, int h, int w, int arr[3001][3001]) {
    int i,j,k,l;
    int ans=n*m;
    int limit=h*w/2+1;
    //cout<<limit<<" "<<ans<<endl;
    for(i=0;i<n-h+1;i++){
        set<pi> s;
        for(j=0;j<h;j++)
            for(k=0;k<w-1;k++){
               // cout<<j<<" "<<k<<endl;
                auto it = s.end();

                if(s.size())
                    it--;
                if(s.size()<limit && arr[i+j][k]<ans)
                    s.insert({arr[i+j][0+k],(i+j)*m+k});
                else if((*it).F>arr[i+j][0+k]){
                    //cout<<(*it).F<<endl;
                    s.erase(it);
                    s.insert({arr[i+j][0+k],(i+j)*m+k});
                }
            }
/// g++ grader.cpp quality.cpp
///  D:\OneDrive\OneDrive\Documents\Competitive Programing\OI Problems\quality
       // for(auto x : s)
       //     cout<<x.F<<"-"<<x.S<<"  ";
       // cout<<"start"<<endl;

        for(j=0;j<m-w+1;j++){




            for(k=0;k<h;k++){
                //cout<<arr[i+k][j+w-1]<<endl;
                auto it = s.end();
                if(s.size())
                    it--;

                if(s.size()<limit && arr[i+k][j+w-1]<ans)
                    s.insert({arr[i+k][j+w-1],(i+k)*m+j+w-1});
                else if((*it).F>arr[i+k][j+w-1]){
                    s.erase(it);
                    s.insert({arr[i+k][j+w-1],(i+k)*m+j+w-1});
                }

               // for(auto x : s)
               //     cout<<x.F<<"-"<<x.S<<"  ";
              //  cout<<endl;


            }
            auto it = s.end();
            if(s.size())
                it--;

            if(s.size()==limit)
                ans=min(ans,(*it).F);


            for(k=0;k<h;k++){

                s.erase({arr[i+k][j],(i+k)*m+j});
             //   s.erase(s.find())
            }

        }

    }
    return ans;

}

Compilation message

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:36:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(s.size()<limit && arr[i+j][k]<ans)
                    ~~~~~~~~^~~~~~
quality.cpp:61:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(s.size()<limit && arr[i+k][j+w-1]<ans)
                    ~~~~~~~~^~~~~~
quality.cpp:78:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(s.size()==limit)
                ~~~~~~~~^~~~~~~
quality.cpp:23:15: warning: unused variable 'l' [-Wunused-variable]
     int i,j,k,l;
               ^

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 34 ms 896 KB Output is correct
5 Correct 33 ms 896 KB Output is correct
6 Correct 30 ms 896 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 34 ms 896 KB Output is correct
5 Correct 33 ms 896 KB Output is correct
6 Correct 30 ms 896 KB Output is correct
7 Correct 1185 ms 3072 KB Output is correct
8 Correct 903 ms 3412 KB Output is correct
9 Correct 996 ms 2732 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 34 ms 896 KB Output is correct
5 Correct 33 ms 896 KB Output is correct
6 Correct 30 ms 896 KB Output is correct
7 Correct 1185 ms 3072 KB Output is correct
8 Correct 903 ms 3412 KB Output is correct
9 Correct 996 ms 2732 KB Output is correct
10 Execution timed out 5069 ms 20856 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 34 ms 896 KB Output is correct
5 Correct 33 ms 896 KB Output is correct
6 Correct 30 ms 896 KB Output is correct
7 Correct 1185 ms 3072 KB Output is correct
8 Correct 903 ms 3412 KB Output is correct
9 Correct 996 ms 2732 KB Output is correct
10 Execution timed out 5069 ms 20856 KB Time limit exceeded
11 Halted 0 ms 0 KB -