oj.uz

답안 #286687

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
286687 2020-08-30T18:09:19 Z FEDIKUS 삶의 질 (IOI10_quality) C++17
60 / 100
 5000 ms 54380 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define xx first
#define yy second
#define srt(a) sort(a.begin(),a.end());
#define srtg(a,int) sort(a.begin(),a.end(),greater<int>())
#define lb(a,x) lower_bound(a.begin(),a.end(),x)
#define up(a,x) upper_bound(a.begin(),a.end(),x)
#define fnd(a,x) find(a.begin(),a.end(),x)
#define vstart auto startt=chrono::system_clock::now()
#define vend auto endd=chrono::system_clock::now()
#define vvreme chrono::duration<double> vremee=endd-startt
#define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#include "quality.h"

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef string str;

vector<int> fwt;

void dodaj(int x,int koliko){
    for(;x<fwt.size();x+=x&-x) fwt[x]+=koliko;
}

int upit(int x){
    int ret=0;
    for(;x>0;x-=x&-x) ret+=fwt[x];
    return ret;
}

int tren(int H,int W){
    int l=1;
    int r=fwt.size()-1;
    //cout<<"     "<<upit(fwt.size()-1)<<endl;
    int naj=-1;
    while(l<=r){
        int mid=l+(r-l)/2;
        int sta=upit(mid);
        if(sta>W*H/2+1){
            r=mid-1;
        }else if(sta==W*H/2+1){
            naj=mid;
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    return naj;
}

void uradi(int i1,int i2,int j,int koliko,int** novoQ){
    for(;i1<=i2;i1++){
        dodaj(novoQ[i1][j],koliko);
    }
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    int ret=INT_MAX;
    fwt.resize(R*C+1,0);
    int** novoQ=new int*[3001];
    for(int i=0;i<=3000;i++){
        novoQ[i]=new int[3001];
    }
    for(int i=0;i<=3000;i++){
        for(int j=0;j<3000;j++) novoQ[i][j]=Q[i][j];
    }
    for(int i=0;i<=R-H;i++){
        for(int j=0;j<W;j++){
            uradi(i,i+H-1,j,1,novoQ);
        }
        ret=min(ret,tren(H,W));
        //cout<<i<<" "<<W-1<<" "<<tren(H,W)<<endl;
        for(int j=W;j<C;j++){
            uradi(i,i+H-1,j-W,-1,novoQ);
            uradi(i,i+H-1,j,1,novoQ);
            ret=min(ret,tren(H,W));
            //cout<<i<<" "<<j<<" "<<tren(H,W)<<endl;
        }
        for(int j=C-1;j>=C-W;j--){
            uradi(i,i+H-1,j,-1,novoQ);
            //cout<<i<<" "<<j<<" "<<tren(H,W)<<endl;
        }
    }
    return ret;
}

Compilation message

quality.cpp: In function 'void dodaj(int, int)':
quality.cpp:30:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(;x<fwt.size();x+=x&-x) fwt[x]+=koliko;
      |          ~^~~~~~~~~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 35832 KB Output is correct
2 Correct 30 ms 35816 KB Output is correct
3 Correct 29 ms 35832 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 35832 KB Output is correct
2 Correct 30 ms 35816 KB Output is correct
3 Correct 29 ms 35832 KB Output is correct
4 Correct 44 ms 36256 KB Output is correct
5 Correct 43 ms 36248 KB Output is correct
6 Correct 43 ms 36224 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 35832 KB Output is correct
2 Correct 30 ms 35816 KB Output is correct
3 Correct 29 ms 35832 KB Output is correct
4 Correct 44 ms 36256 KB Output is correct
5 Correct 43 ms 36248 KB Output is correct
6 Correct 43 ms 36224 KB Output is correct
7 Correct 463 ms 38168 KB Output is correct
8 Correct 464 ms 38176 KB Output is correct
9 Correct 429 ms 38008 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 35832 KB Output is correct
2 Correct 30 ms 35816 KB Output is correct
3 Correct 29 ms 35832 KB Output is correct
4 Correct 44 ms 36256 KB Output is correct
5 Correct 43 ms 36248 KB Output is correct
6 Correct 43 ms 36224 KB Output is correct
7 Correct 463 ms 38168 KB Output is correct
8 Correct 464 ms 38176 KB Output is correct
9 Correct 429 ms 38008 KB Output is correct
10 Execution timed out 5035 ms 54380 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 35832 KB Output is correct
2 Correct 30 ms 35816 KB Output is correct
3 Correct 29 ms 35832 KB Output is correct
4 Correct 44 ms 36256 KB Output is correct
5 Correct 43 ms 36248 KB Output is correct
6 Correct 43 ms 36224 KB Output is correct
7 Correct 463 ms 38168 KB Output is correct
8 Correct 464 ms 38176 KB Output is correct
9 Correct 429 ms 38008 KB Output is correct
10 Execution timed out 5035 ms 54380 KB Time limit exceeded
11 Halted 0 ms 0 KB -