답안 #917508

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
917508 2024-01-28T11:00:55 Z 8pete8 UFO (IZhO14_ufo) C++17
100 / 100
710 ms 172668 KB
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
using namespace std;
const int mod=1e9+7,mxn=1e6+5,Mxn=1e8,inf=1e9,minf=-1e9,lg=30;
int n,m,r,k,p;
void setIO(string name){		
	ios_base::sync_with_stdio(0); cin.tie(0);		
	freopen((name+".in").c_str(),"r",stdin);		
	freopen((name+".out").c_str(),"w",stdout);	
}
struct seg{
    vector<int>v;
    void init(int n){v.resize(4*n+4,minf);}
    void upd(int l,int r,int pos,int val,int up){
        if(l==r)return void(v[pos]=val);
        int mid=l+(r-l)/2;
        if(up<=mid)upd(l,mid,pos*2,val,up);
        else upd(mid+1,r,pos*2+1,val,up);
        v[pos]=max(v[pos*2],v[pos*2+1]);
    }
    void update(int pos,int val,int n){
        upd(1,n,1,val,pos);
    }
    int qry1(int l,int r,int ql,int qr,int h,int pos){
        int mid=l+(r-l)/2;
        if(l>qr||r<ql)return inf;
        if(v[pos]<h)return inf;
        if(l==r)return r;
        int ans=qry1(l,mid,ql,qr,h,pos*2);
        if(ans!=inf)return ans;
        return qry1(mid+1,r,ql,qr,h,pos*2+1);
    }
   int qry2(int l,int r,int ql,int qr,int h,int pos){
        int mid=l+(r-l)/2;
        if(l>qr||r<ql)return inf;
        if(v[pos]<h)return inf;
        if(l==r)return r;
        int ans=qry2(mid+1,r,ql,qr,h,pos*2+1);
        if(ans!=inf)return ans;
        return qry2(l,mid,ql,qr,h,pos*2);
    }
}t[2][mxn+10];
int get1(int d,int h,int n,int p,int last){
    return t[d][p].qry1(1,n,last+1,n,h,1);
}
int get2(int d,int h,int n,int p,int last){
    return t[d][p].qry2(1,n,1,last-1,h,1);
}
int32_t main(){
    fastio
    cin>>n>>m>>r>>k>>p;
    vector<vector<int>>grid(n+1,vector<int>(m+1,0));
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>grid[i][j];
    for(int i=1;i<=n;i++){
        t[0][i].init(m);
        for(int j=1;j<=m;j++)t[0][i].update(j,grid[i][j],m);
    }
    for(int j=1;j<=m;j++){
        t[1][j].init(n);
        for(int i=1;i<=n;i++)t[1][j].update(i,grid[i][j],n);
    }
    int d=0,sz=0,cnt,last,x,y;
    bool yes=false;
    while(k--){
        char g;cin>>g;
        int p,h;cin>>p>>h;
        if(g=='W'||g=='E')d=0,sz=m;
        else d=1,sz=n;
        if(g=='W'||g=='N')yes=true,last=0;
        else yes=false,last=sz+1;
        cnt=r;
        while(cnt--){
            last=((yes)?get1(d,h,sz,p,last):get2(d,h,sz,p,last));
            if(last==inf||last==minf)break;
            x=p,y=last;
            if(d)swap(x,y);
            grid[x][y]--;
            t[0][x].update(y,grid[x][y],m);
            t[1][y].update(x,grid[x][y],n);
        }
    }
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)grid[i][j]+=grid[i][j-1]+grid[i-1][j]-grid[i-1][j-1];
    int ans=0;
    for(int i=p;i<=n;i++)for(int j=p;j<=m;j++)ans=max(ans,grid[i][j]-grid[i-p][j]-grid[i][j-p]+grid[i-p][j-p]);
    cout<<ans;
}

Compilation message

ufo.cpp:31:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   31 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
ufo.cpp:36:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   36 | void setIO(string name){
      |                       ^
ufo.cpp:43:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   43 |     void init(int n){v.resize(4*n+4,minf);}
      |                    ^
ufo.cpp:44:48: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   44 |     void upd(int l,int r,int pos,int val,int up){
      |                                                ^
ufo.cpp:51:38: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   51 |     void update(int pos,int val,int n){
      |                                      ^
ufo.cpp:54:53: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   54 |     int qry1(int l,int r,int ql,int qr,int h,int pos){
      |                                                     ^
ufo.cpp:63:52: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   63 |    int qry2(int l,int r,int ql,int qr,int h,int pos){
      |                                                    ^
ufo.cpp:73:42: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   73 | int get1(int d,int h,int n,int p,int last){
      |                                          ^
ufo.cpp:76:42: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   76 | int get2(int d,int h,int n,int p,int last){
      |                                          ^
ufo.cpp:79:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   79 | int32_t main(){
      |              ^
ufo.cpp: In function 'void setIO(std::string)':
ufo.cpp:38:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ufo.cpp:39:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 47196 KB Output is correct
2 Correct 16 ms 47444 KB Output is correct
3 Correct 16 ms 47452 KB Output is correct
4 Correct 24 ms 47964 KB Output is correct
5 Correct 75 ms 51240 KB Output is correct
6 Correct 154 ms 82004 KB Output is correct
7 Correct 242 ms 123452 KB Output is correct
8 Correct 197 ms 123384 KB Output is correct
9 Correct 437 ms 120776 KB Output is correct
10 Correct 462 ms 123200 KB Output is correct
11 Correct 351 ms 121764 KB Output is correct
12 Correct 489 ms 123200 KB Output is correct
13 Correct 593 ms 126504 KB Output is correct
14 Correct 410 ms 121780 KB Output is correct
15 Correct 427 ms 123200 KB Output is correct
16 Correct 213 ms 121708 KB Output is correct
17 Correct 604 ms 126288 KB Output is correct
18 Correct 201 ms 118188 KB Output is correct
19 Correct 279 ms 128840 KB Output is correct
20 Correct 710 ms 172668 KB Output is correct