Submission #908916

#	Time	Username	Problem	Language	Result	Execution time	Memory
908916		MilosMilutinovic	Rope (JOI17_rope)	C++14	0 / 100	2 ms	436 KiB

rope

#include<bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
 
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
 
ll readint(){
	ll x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int n,m,a[150];

int main() {
	n=readint(); m=readint();
	for(int i=1;i<=n;i++) a[i]=readint();
	for(int c=1;c<=m;c++){
		int res=1e9;
		for(int f=1;f<=m;f++){
			vector<vector<vector<vector<int>>>> dp(2,vector<vector<vector<int>>>(2,vector<vector<int>>(2,vector<int>(2,1e9))));
			dp[1][0][0][0]=(a[1]==c?0:1);
			dp[0][1][1][0]=(a[1]==f?0:1);
			for(int i=2;i<=n;i++){
				for(int prv=0;prv<2;prv++){
					int cnt=0;
					for(int j=i;j<=n;j++) cnt+=(a[j]!=(prv==0?f:c));
					int mn=1e9;
					for(int x=0;x<2;x++) for(int y=0;y<2;y++) for(int z=0;z<2;z++){
						if(x==1&&y==1&&z==0) continue;
						mn=min(mn,dp[x][y][prv][z]);
					}
					res=min(res,cnt+mn);
				}
				vector<vector<vector<vector<int>>>> ndp(2,vector<vector<vector<int>>>(2,vector<vector<int>>(2,vector<int>(2,1e9))));
				for(int sx=0;sx<2;sx++){
					for(int sy=0;sy<2;sy++){
						for(int prv=0;prv<2;prv++){
							for(int fir=0;fir<2;fir++){
								for(int cur=0;cur<2;cur++){
									if(sx==1&&sy==1&&fir==0&&cur!=prv) continue;
									if(sx==1&&sy==1&&fir==1&&cur==prv) continue;
									int val=(cur==0?c:f);
									chkmin(ndp[sx|(cur==0?1:0)][sy|(cur==1?1:0)][cur][prv==cur?1:0],dp[sx][sy][prv][fir]+(a[i]==val?0:1));
								}
							}
						}
					}
				}
				swap(dp,ndp);
			}
		}
		printf("%d\n",res);
	}
	return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 30
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 20