제출 #559848

#제출 시각아이디문제언어결과실행 시간메모리
559848_BodyLinear Garden (IOI08_linear_garden)C++17
100 / 100
266 ms2416 KiB
#include<bits/stdc++.h> #define int long long using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int rand(int l, int r){ uniform_int_distribution<int> uid(l, r); return uid(rng); } string s; int N,M; int dp[(int)(1e6+4)][2][5][5][5]; int DP() { for(int i=N;i>=0;i--) { for(int tight=0;tight<2;tight++) { for(int mn=0;mn<=2;mn++) { for(int mx=2;mx<=4;mx++) { if(mx-mn>2) continue; for(int where=mn;where<=mx;where++) { if(tight) { int &ret=dp[i&1][1][mn][mx][where]; ret=0; if(i==N){ ret=1; continue; } for(int d=0;d<=s[i]-'0';d++) { if(d==s[i]-'0') { if(d==0&&where-1>=0) ret+=dp[(i+1)&1][1][min(mn,where-1)][mx][where-1]; else if(d==1&&where+1<5) ret+=dp[(i+1)&1][1][mn][max(mx,where+1)][where+1]; } else { if(d==0&&where-1>=0) ret+=dp[(i+1)&1][0][min(mn,where-1)][mx][where-1]; else if(d==1&&where+1<5) ret+=dp[(i+1)&1][0][mn][max(mx,where+1)][where+1]; } ret=ret%M; } } else { int &ret=dp[i&1][0][mn][mx][where]; ret=0; if(i==N){ ret=1; continue; } for(int d=0;d<=1;d++) { if(d==s[i]-'0') { if(d==0&&where-1>=0) ret+=dp[(i+1)&1][0][min(mn,where-1)][mx][where-1]; else if(d==1&&where+1<5) ret+=dp[(i+1)&1][0][mn][max(mx,where+1)][where+1]; } else { if(d==0&&where-1>=0) ret+=dp[(i+1)&1][0][min(mn,where-1)][mx][where-1]; else if(d==1&&where+1<5) ret+=dp[(i+1)&1][0][mn][max(mx,where+1)][where+1]; } ret=ret%M; } } } } } } } return dp[0][1][2][2][2]; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); // freopen("team.in","r",stdin); // freopen("team.out","w",stdout); int tt=1; // cin>>tt; int T=1; while(tt--) { cin>>N>>M; cin>>s; for(int i=0;i<N;i++) { if(s[i]=='L') s[i]='0'; else s[i]='1'; } cout<<DP()<<"\n"; //cout<<s<<"\n"; } } /*stolen stuff you should look for * int overflow, array bounds * special cases (n=1?) * do smth instead of nothing and stay organized * WRITE STUFF DOWN * DON'T GET STUCK ON ONE APPROACH */

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

linear_garden.cpp: In function 'int32_t main()':
linear_garden.cpp:93:5: warning: unused variable 'T' [-Wunused-variable]
   93 | int T=1;
      |     ^
#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...
#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...
#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...
#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...