답안 #103185

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
103185	2019-03-29T07:47:58 Z	aesfasfasf	UFO (IZhO14_ufo)	C++14	35 / 100	907 ms	263168 KB

ufo

#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1e6 + 5;
int n,m,r,k,p;
vector<vector<int>> a;
vector<int> temp;
int remain;
struct segtree{
    
    vector<int> v1;
    int n;
    
    void reset(int n) {
        this -> n = n;
        v1.resize((n * 6) + 10);
        
    }
    void update(int curr,int l,int r,int u,int val){
       // cout<<l<<" "<<r<<endl;
        if(l == r){
            v1[curr] = val;
            return;
        }
        int mid = (l+r)/2;
        if(u<=mid){
            update(2*curr,l,mid,u,val);
        }else{
            update(2*curr+1,mid+1,r,u,val);
        }
        v1[curr] = max(v1[2*curr],v1[2*curr+1]);
    }
    void findfirst(int curr,int l,int r,int x){
        if(remain == 0||v1[curr]<x){
           //cout<<l<<" "<<r<<" "<<v1[curr]<<endl;
            return;
        }
        if(l == r){
            remain--;
            temp.push_back(l);
        }else{
            int mid = (l+r)/2;
            findfirst(2*curr,l,mid,x);
            findfirst(2*curr+1,mid+1,r,x);
        }
    }
    void findlast(int curr,int l,int r,int x){
        if(remain == 0||v1[curr]<x){
           
            return;
        }
        if(l == r){
            remain--;
            temp.push_back(l);
        }else{
            int mid = (l+r)/2;
            findlast(2*curr+1,mid+1,r,x);
            findlast(2*curr,l,mid,x);
        }
    }
};
segtree row[MAXN],col[MAXN];
int main(){
    
    cin>>m>>n>>r>>k>>p;
    
    a.resize(m+1);
    for(int i=1;i<=n;i++){
        col[i].reset(m+1);
    }
    a[0].resize(n+1);
    for(int i=1;i<=m;i++){
        
        row[i].reset(n+1);
        a[i].resize(n+1);
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
           
            row[i].update(1,1,n,j,a[i][j]);
            col[j].update(1,1,n,i,a[i][j]);
        }
    }
    for(int i=0;i<k;i++){
        temp.clear();
        remain = r;
        char z;
        cin>>z;
        int id,h;
        cin>>id>>h;
        if(z == 'W'){
            row[id].findfirst(1,1,n,h);
            for(int x:temp){
                //cout<<x<<endl;
                a[id][x]--;
               
                row[id].update(1,1,n,x,a[id][x]);
                col[x].update(1,1,n,id,a[id][x]);
            }
        }else if(z == 'E'){
            row[id].findlast(1,1,n,h);
            for(int x:temp){
                
                a[id][x]--;
                row[id].update(1,1,n,x,a[id][x]);
                col[x].update(1,1,n,id,a[id][x]);
            }
        }else if(z == 'N'){
            col[id].findfirst(1,1,n,h);
            
            for(int x:temp){
                
                a[x][id]--;
                
                row[x].update(1,1,n,id,a[x][id]);
                col[id].update(1,1,n,x,a[x][id]);
            }
        }else{
            col[id].findlast(1,1,n,h);
            for(int x:temp){
                a[x][id]--;
                
                //cout<<x<<endl;
                row[x].update(1,1,n,id,a[x][id]);
                col[id].update(1,1,n,x,a[x][id]);
            }
        }
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            a[i][j] += a[i-1][j]+a[i][j-1]-a[i-1][j-1];
           
        }
    }
    int ans = 0;
    
   for(int i=1;i<=m-p+1;i++){
        for(int j=1;j<=n-p+1;j++){
            if(i+p-1>m||j+p-1>n){
                continue;
            }
            int temp = a[i+p-1][j+p-1] - a[i+p-1][j-1] - a[i-1][j+p-1] + a[i-1][j-1];
            
            ans = max(ans,temp);
        }
    }
    cout<<ans<<endl;
}

Subtask #1

35.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	63 ms	62968 KB	Output is correct
2	Correct	60 ms	62972 KB	Output is correct
3	Correct	59 ms	63096 KB	Output is correct
4	Correct	91 ms	63608 KB	Output is correct
5	Runtime error	162 ms	131676 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Correct	502 ms	88040 KB	Output is correct
7	Runtime error	302 ms	194956 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	253 ms	194780 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Runtime error	246 ms	183816 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	277 ms	195004 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Runtime error	318 ms	197496 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
12	Runtime error	275 ms	194872 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
13	Correct	683 ms	126532 KB	Output is correct
14	Runtime error	301 ms	197552 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Runtime error	309 ms	194996 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Runtime error	278 ms	197496 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Incorrect	729 ms	126476 KB	Output isn't correct
18	Correct	549 ms	119584 KB	Output is correct
19	Runtime error	397 ms	213496 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Runtime error	907 ms	263168 KB	Execution killed with signal 11 (could be triggered by violating memory limits)