제출 #1084975

#제출 시각아이디문제언어결과실행 시간메모리
10849758pete8웜뱃 (IOI13_wombats)C++17
100 / 100
3789 ms68616 KiB
#include "wombats.h" #include<iostream> #include<stack> #include<map> #include<vector> #include<string> #include<cassert> #include<unordered_map> #include <queue> #include <cstdint> #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 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") const int inf=1e9; int dist[300][202][202],costv[5005][202],costh[5005][200]; int n,m; int pref[202],root,bound; int ans[202][202],what[202][202]; void mul(vector<vector<int>>a,vector<vector<int>>b){ //knuth's op vector<vector<int>>opt(m,vector<int>(m,-1)); for(int i=0;i<m;i++)for(int j=0;j<m;j++)what[i][j]=inf,opt[i][i]=i; for(int i=0;i<m;i++){ for(int j=m-1;j>=0;j--){ int x=0,y=m-1; if(i&&opt[i-1][j]!=-1)x=opt[i-1][j]; if(j+1<m&&opt[i][j+1]!=-1)y=opt[i][j+1]; for(int k=x;k<=y;k++)if(what[i][j]>a[i][k]+b[k][j]){ what[i][j]=a[i][k]+b[k][j]; opt[i][j]=k; } } } } struct seg{ vector<vector<int>>v[1000]; void build(int l,int r,int pos){ v[pos].resize(m,vector<int>(m)); int mid=l+(r-l)/2; if(l==r){ for(int i=0;i<m;i++)for(int j=0;j<m;j++)v[pos][i][j]=dist[l][i][j]; return; } build(l,mid,pos*2); build(mid+1,r,pos*2+1); mul(v[pos*2],v[pos*2+1]); for(int i=0;i<m;i++)for(int j=0;j<m;j++)v[pos][i][j]=what[i][j]; } void update(int l,int r,int qpos,int pos){ int mid=l+(r-l)/2; if(l==r){ for(int i=0;i<m;i++)for(int j=0;j<m;j++)v[pos][i][j]=dist[l][i][j]; return; } if(qpos<=mid)update(l,mid,qpos,pos*2); else update(mid+1,r,qpos,pos*2+1); mul(v[pos*2],v[pos*2+1]); for(int i=0;i<m;i++)for(int j=0;j<m;j++)v[pos][i][j]=what[i][j]; } }t; void cal(int id){ for(int st=0;st<m;st++)for(int go=0;go<m;go++){ if(st!=go)dist[id][st][go]=inf; else dist[id][st][go]=0; } for(int r=(id*root);r<min(n,(id*root)+root);r++)for(int st=0;st<m;st++){ int mncost=inf,add=0; for(int go=0;go<m;go++){ mncost=min(mncost,dist[id][st][go]-add); pref[go]=mncost+add; add+=costh[r][go]; } mncost=inf,add=0; for(int go=m-1;go>=0;go--){ mncost=min(mncost,dist[id][st][go]-add); dist[id][st][go]=min(pref[go],mncost+add); if(r!=n-1)dist[id][st][go]+=costv[r][go]; if(go)add+=costh[r][go-1]; } } } void init(int R, int C, int H[5000][200], int V[5000][200]){ n=R,m=C; //root=sqrt(n); root=60; bound=((n-1)/root); for(int i=0;i<n;i++)for(int j=0;j<m-1;j++)costh[i][j]=H[i][j]; for(int i=0;i<n-1;i++)for(int j=0;j<m;j++)costv[i][j]=V[i][j]; for(int i=0;i<=bound;i++)cal(i); t.build(0,bound,1); } void changeH(int P, int Q, int W){ costh[P][Q]=W; cal(P/root); t.update(0,bound,P/root,1); } void changeV(int P, int Q, int W){ costv[P][Q]=W; cal(P/root); t.update(0,bound,P/root,1); } int escape(int V1, int V2){ return t.v[1][V1][V2]; } //70x200x200x500 /* we can compute [start][at][row] =200x200x5000 for each update how to improve? use segtree? and matrix [from][go] 200x200 too much memory? do sqrt decomp instead? trading time for space split block what if we combine both sqrt and segtree 'o'? we can do qry in */

컴파일 시 표준 에러 (stderr) 메시지

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~
wombats.cpp:33:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   33 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
wombats.cpp:39:51: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   39 | void mul(vector<vector<int>>a,vector<vector<int>>b){
      |                                                   ^
wombats.cpp:57:35: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   57 |     void build(int l,int r,int pos){
      |                                   ^
wombats.cpp:69:45: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   69 |     void update(int l,int r,int qpos,int pos){
      |                                             ^
wombats.cpp:81:16: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   81 | void cal(int id){
      |                ^
wombats.cpp:102:59: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  102 | void init(int R, int C, int H[5000][200], int V[5000][200]){
      |                                                           ^
wombats.cpp:113:33: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  113 | void changeH(int P, int Q, int W){
      |                                 ^
wombats.cpp:118:33: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  118 | void changeV(int P, int Q, int W){
      |                                 ^
wombats.cpp:123:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  123 | int escape(int V1, int V2){
      |                          ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...