oj.uz

Submission #908916

# Submission time Handle Problem Language Result Execution time Memory
908916 2024-01-17T01:57:33 Z MilosMilutinovic Rope (JOI17_rope) C++14
0 / 100
 2 ms 436 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 436 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 436 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 436 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 436 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 436 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -