# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
264782 | 2020-08-14T09:36:25 Z | Nucleist | Linear Garden (IOI08_linear_garden) | C++14 | 1203 ms | 19680 KB |
//Self-control leads to consistency. #include <bits/stdc++.h> using namespace std; #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #define flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) #define debug(x) cerr << " - " << #x << ": " << x << endl; #define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl; #define all(x) (x).begin(),(x).end() #define sz(x) (ll)x.size() #define ll long long #define INF 1000000000 #define MOD 1000000007 #define pb push_back #define ve vector<ll> #define dos pair<ll,ll> #define vedos vector<dos> #define rand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) #define EPS 0.000001 struct greateri { template<class T> bool operator()(T const &a, T const &b) const { return a > b; } }; void setIO(string s) { ios_base::sync_with_stdio(0); cin.tie(0); freopen((s+".in").c_str(),"r",stdin); freopen((s+".out").c_str(),"w",stdout); } ll n,m; ll dp[2][5][5][5]; ve hed; ll ans=0; int main() { //flash; cin>>n; cin>>m; string in; cin>>in; ll dif=0; ll low1=0; ll high1=0; ll rank=0; ll last=n-1; vector<pair<dos,dos>>g; for (ll i = 0; i < sz(in); ++i) { if(in[i]=='P' && abs(dif-high1+1)<=2 && abs(dif-low1+1)<=2 && abs(dif+1)<=2){ g.pb({{i,max(high1,dif+1)},{min(low1,dif+1),dif+1}}); //rank=(rank+dp[{{i,max(high1,dif+1)},{min(low1,dif+1),dif+1}}])%m; } if(in[i]=='L'){ dif++; high1=max(high1,dif); low1=min(low1,dif); } else { dif--; low1=min(low1,dif); high1=max(high1,dif); } } reverse(all(g)); for(auto it:g){ int i=it.first.first; high1=it.first.second; low1=it.second.first; dif=it.second.second; while(last>=i){ for (ll high = -2; high <= 2; ++high) { for (ll low = -2; low <= 2; ++low) { for (ll cur = -2; cur <= 2; ++cur) { ll ans=0; if(last==n-1){ dp[last%2][high+2][low+2][cur+2]=1;continue; } if(abs(cur-high+1)<=2 && abs(cur-low+1)<=2 && abs(cur+1)<=2){ ll sol=cur+1; ans=(ans+dp[(last+1)%2][max(high,sol)+2][min(low,sol)+2][sol+2])%m; } if(abs(cur-high-1)<=2 && abs(cur-low-1)<=2 && abs(cur-1)<=2){ ll sol=cur-1; ans=(ans+dp[(last+1)%2][max(high,sol)+2][min(low,sol)+2][sol+2])%m; } dp[(last)%2][high+2][low+2][cur+2]=ans%m; } } } last--; } rank=(rank+dp[i%2][high1+2][low1+2][dif+2])%m; } cout<<(rank+1)%m; return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 256 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 256 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 256 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | Output is correct |
2 | Correct | 1 ms | 256 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Correct | 7 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 31 ms | 768 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 31 ms | 640 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 74 ms | 1656 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 94 ms | 1656 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 368 ms | 5264 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 487 ms | 3472 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 623 ms | 5988 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 724 ms | 10276 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1170 ms | 19680 KB | Output is correct |
2 | Correct | 1203 ms | 11492 KB | Output is correct |
3 | Correct | 1200 ms | 19680 KB | Output is correct |