Submission #243585

#	Time	Username	Problem	Language	Result	Execution time	Memory
243585		Dremix10	Quality Of Living (IOI10_quality)	C++17	60 / 100	5069 ms	20856 KiB

quality

#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 (stderr)

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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20