# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
389373 | 2021-04-14T03:44:24 Z | i_am_noob | Binary Subsequences (info1cup17_binary) | C++17 | 164 ms | 59424 KB |
#include<bits/stdc++.h> using namespace std; #define ll long long //#define int ll #define rep(n) rep1(i,n) #define rep1(i,n) rep2(i,0,n) #define rep2(i,a,b) for(int i=a; i<(b); ++i) #define rep3(i,a,b) for(int i=a; i>=(b); --i) #define pb push_back #define pii pair<int,int> #define sz(a) ((int)a.size()) #define all(a) a.begin(),a.end() #define pow2(x) (1ll<<(x)) #define inf 0x3f3f3f3f #ifdef i_am_noob #define bug(...) cerr << "#" << __LINE__ << " " << #__VA_ARGS__ << "- ", _do(__VA_ARGS__) template<typename T> void _do(T x){cerr << x << endl;} template<typename T, typename ...S> void _do(T x, S... y){cerr << x << ", ";_do(y...);} #else #define bug(...) 49 #endif const int maxn=2005,mod=1000000007; int n=2000,dp[maxn][maxn],minn[maxn][maxn],val1[maxn][maxn],val2[maxn][maxn],ans[maxn]; void add(int& x, int y){ x+=y; if(x>=mod) x-=mod; } signed main(){ ios_base::sync_with_stdio(0),cin.tie(0); dp[1][0]=1; rep2(i,1,n+2) rep1(j,n+2) minn[i][j]=inf; minn[1][0]=0; rep2(i,1,n+2) rep1(j,n+2){ if(2*i-j>=0&&2*i-j<maxn){ add(dp[2*i-j][i],dp[i][j]); if(minn[i][j]+1<minn[2*i-j][i]){ minn[2*i-j][i]=minn[i][j]+1; val1[2*i-j][i]=i; val2[2*i-j][i]=j; } } if(i+j+1>=0&&i+j+1<maxn){ add(dp[i+j+1][j],dp[i][j]); if(minn[i][j]+1<minn[i+j+1][j]){ minn[i+j+1][j]=minn[i][j]+1; val1[i+j+1][j]=i; val2[i+j+1][j]=j; } } add(ans[i],dp[i][j]); } rep2(i,2,n+2){ cout << ans[i] << "\n"; int k=inf,minid; rep1(j,n+2) if(minn[i][j]<k) k=minn[i][j],minid=j; int x=i,y=minid; vector<int> vec; while(x>1){ if(val1[x][y]==y) vec.pb(0); else vec.pb(1); int tmp1=val1[x][y],tmp2=val2[x][y]; x=tmp1,y=tmp2; } for(auto i: vec) cout << i << ' '; cout << "\n"; } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 164 ms | 59424 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 162 ms | 59336 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 161 ms | 59412 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |