Submission #112964

#TimeUsernameProblemLanguageResultExecution timeMemory
112964shashwatchandraGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++17
0 / 100
2 ms384 KiB
/*input 6 RRRRRG */ #include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define int long long #define double long double #define f first #define s second #define mp make_pair #define pb push_back #define RE(i,n) for (int i = 1; i <= n; i++) #define RED(i,n) for (int i = n; i > 0; i--) #define REPS(i,n) for(int i = 1; (i*i) <= n; i++) #define REP(i,n) for (int i = 0; i < (int)n; i++) #define FOR(i,a,b) for (int i = a; i < b; i++) #define REPD(i,n) for (int i = n-1; i >= 0; i--) #define FORD(i,a,b) for (int i = a; i >= b; i--) #define all(v) v.begin(),v.end() #define pii pair<int,int> #define vi vector<int> #define vvi vector<vi> #define print(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout << *it << " "; cout << endl; #define debug(x) cout << x << endl; #define debug2(x,y) cout << x << " " << y << endl; #define debug3(x,y,z) cout << x << " " << y << " " << z << endl; typedef tree< int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; const int INF = 1e18+1; const int MOD = 1e9+7; const double PI = 3.14159265358979323846264338; int raise(int a,int n,int m = MOD){ if(n == 0)return 1; if(n == 1)return a; int x = 1; x *= raise(a,n/2,m); x %= m; x *= x; x %= m; if(n%2)x*= a; x %= m; return x; } int floor1(int n,int k){ if(n%k == 0 || n >= 0)return n/k; return (n/k)-1; } int ceil1(int n,int k){ return floor1(n+k-1,k); } const int N = 201; int a[N]; vector<int> x[3]; int n; int dp[N][N][N][3]; void solve(){ cin >> n; REP(i,n){ char o;cin >> o; if(o == 'R')a[i] = 0; else if(o == 'G')a[i] = 1; else a[i] = 2; //cout << a[i] << " "; x[a[i]].pb(i); } for(int i = 0;i < 3;i++){ if(2*x[i].size() > n){ cout << -1; return; } } // cout << endl; //dp[i][j][k] means used i red , j green and k yellow. dp[0][0][0][0] = 0; dp[0][0][0][1] = 0; dp[0][0][0][2] = 0; REP(i,N){ REP(j,N){ REP(k,N){ REP(l,3){ if(i+j+k)dp[i][j][k][l] = INF; } } } } for(int i = 0;i <= x[0].size();i++){ for(int j = 0;j <= x[1].size();j++){ for(int k = 0;k <= x[2].size();k++){ int ind = i+j+k; for(int prev = 0;prev < 3;prev++){ if(dp[i][j][k][prev] != INF){ } for(int cur = 0;cur < 3;cur++){ if(prev == cur)continue; if(cur == 0 and i == x[cur].size())continue; if(cur == 1 and j == x[cur].size())continue; if(cur == 2 and k == x[cur].size())continue; if(cur == 0)dp[i+1][j][k][cur] = min(dp[i+1][j][k][cur],dp[i][j][k][prev]+abs(ind-x[cur][i])); if(cur == 1)dp[i][j+1][k][cur] = min(dp[i][j+1][k][cur],dp[i][j][k][prev]+abs(ind-x[cur][j])); if(cur == 2)dp[i][j][k+1][cur] = min(dp[i][j][k+1][cur],dp[i][j][k][prev]+abs(ind-x[cur][k])); } } } } } int ans = INF; for(int i = 0;i < 3;i++){ //cout << dp[x[0].size()][x[1].size()][x[2].size()][i] << endl; ans = min(ans,dp[x[0].size()][x[1].size()][x[2].size()][i]); } if(ans == INF){ cout << -1; return; } cout << ans/2 << endl; } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //freopen(".in","r",stdin);freopen(".out","w",stdout); int t = 1; //cin >> t; while(t--){ solve(); } return 0; }

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'void solve()':
joi2019_ho_t3.cpp:86:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(2*x[i].size() > n){
        ~~~~~~~~~~~~~~^~~
joi2019_ho_t3.cpp:105:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0;i <= x[0].size();i++){
                  ~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:106:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0;j <= x[1].size();j++){
                   ~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:107:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int k = 0;k <= x[2].size();k++){
                    ~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:114:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(cur == 0 and i == x[cur].size())continue;
                         ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:115:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(cur == 1 and j == x[cur].size())continue;
                         ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:116:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(cur == 2 and k == x[cur].size())continue;
                         ~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...