답안 #917497

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
917497 2024-01-28T10:33:41 Z 8pete8 UFO (IZhO14_ufo) C++17
95 / 100
2000 ms 102188 KB
#include<stdio.h>
#include<stack>
#include<map>
#include<vector>
#include<iostream>
#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,bruh;
struct seg{
    vector<int>v;
    void init(int n){v.resize(2*n+2,minf);}
    void update(int pos,int val,int n){
        pos+=n+1;
        v[pos]=val;
        for(int i=pos;i>0;i>>=1)v[i>>1]=max(v[i],v[i^1]);
    }
    int qry(int l,int r,int n){
        int ans=minf;
        for(l+=n+1,r+=n+1;l<=r;l>>=1,r>>=1){
            if(l&1)ans=max(ans,v[l++]);
            if(!(r&1))ans=max(ans,v[r--]);
        }
        return ans;
    }
}t[2][mxn+10];
int get1(int d,int h,int n,int p,int last){
    int l=last+1,r=n,mid=0,ans=inf;
    while(l<=r){
        mid=l+(r-l)/2;
        if(t[d][p].qry(last+1,mid,n)>=h)ans=min(ans,mid),r=mid-1;
        else l=mid+1;
    }
    return ans;
}
int get2(int d,int h,int n,int p,int last){
    int l=1,r=last-1,mid=0,ans=minf;
    while(l<=r){
        mid=l+(r-l)/2;
        if(t[d][p].qry(mid,last-1,n)>=h)ans=max(ans,mid),l=mid+1;
        else r=mid-1;
    }
    return ans;
}
int32_t main(){
    scanf("%d %d %d %d %d",&n,&m,&r,&k,&p);
    vector<vector<ll>>grid(n+1,vector<ll>(m+1,0));
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%lld",&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,po,h;
    char g;
    bool yes=false;
    while(k--){
        scanf(" %c %d %d",&g,&po,&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,po,last):get2(d,h,sz,po,last));
            if(last==inf||last==minf)break;
            x=po,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];
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)grid[i][j]+=grid[i-1][j];
    ll 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]);
    printf("%lld",ans);
}

Compilation message

ufo.cpp:33:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   33 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
ufo.cpp:40:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   40 |     void init(int n){v.resize(2*n+2,minf);}
      |                    ^
ufo.cpp:41:38: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   41 |     void update(int pos,int val,int n){
      |                                      ^
ufo.cpp:46:30: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   46 |     int qry(int l,int r,int n){
      |                              ^
ufo.cpp:55:42: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   55 | int get1(int d,int h,int n,int p,int last){
      |                                          ^
ufo.cpp:64:42: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   64 | int get2(int d,int h,int n,int p,int last){
      |                                          ^
ufo.cpp:73:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   73 | int32_t main(){
      |              ^
ufo.cpp: In function 'int32_t main()':
ufo.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |     scanf("%d %d %d %d %d",&n,&m,&r,&k,&p);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ufo.cpp:76:52: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%lld",&grid[i][j]);
      |                                               ~~~~~^~~~~~~~~~~~~~~~~~~~
ufo.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         scanf(" %c %d %d",&g,&po,&h);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 47192 KB Output is correct
2 Correct 14 ms 47196 KB Output is correct
3 Correct 17 ms 47448 KB Output is correct
4 Correct 30 ms 47452 KB Output is correct
5 Correct 118 ms 48668 KB Output is correct
6 Correct 223 ms 59012 KB Output is correct
7 Correct 340 ms 73256 KB Output is correct
8 Correct 290 ms 73024 KB Output is correct
9 Correct 812 ms 71880 KB Output is correct
10 Correct 1145 ms 73284 KB Output is correct
11 Correct 784 ms 73016 KB Output is correct
12 Correct 1294 ms 73284 KB Output is correct
13 Correct 1313 ms 76380 KB Output is correct
14 Correct 878 ms 72616 KB Output is correct
15 Correct 1921 ms 73252 KB Output is correct
16 Correct 348 ms 72776 KB Output is correct
17 Execution timed out 2073 ms 76372 KB Time limit exceeded
18 Correct 322 ms 75344 KB Output is correct
19 Correct 665 ms 77272 KB Output is correct
20 Correct 1340 ms 102188 KB Output is correct