Submission #560063

#TimeUsernameProblemLanguageResultExecution timeMemory
560063Killer2501Growing Vegetable is Fun 3 (JOI19_ho_t3)C++14
100 / 100
80 ms121676 KiB
#include <bits/stdc++.h> #define ll int #define pb push_back #define task "bus" #define pll pair<ll, ll> #define pii pair<ll, pll> #define fi first #define se second const ll mod = 1e9+7; const ll N = 405; const ll base = 250; using namespace std; ll n, m, t, k, T, ans, a[N],tong, b[N], c[N], d[N], dp[N][N][N][4], cnt[N][N][4][4], n1, n2, n3; string s; void sol() { cin >> n >> s; for(int i = 0; i < n; i ++) { if(s[i] == 'R')a[++n1] = i+1; else if(s[i] == 'Y')b[++n2] = i+1; else c[++n3] = i+1; } for(int i = 1; i <= n1; i ++) { k = 0; for(int j = 1; j <= n2; j ++) { if(b[j] > a[i])++k; cnt[i][j][1][2] = k; } k = 0; for(int j = 1; j <= n3; j ++) { if(c[j] > a[i])++k; cnt[i][j][1][3] = k; } } for(int i = 1; i <= n2; i ++) { k = 0; for(int j = 1; j <= n1; j ++) { if(a[j] > b[i])++k; cnt[i][j][2][1] = k; } k = 0; for(int j = 1; j <= n3; j ++) { if(c[j] > b[i])++k; cnt[i][j][2][3] = k; } } for(int i = 1; i <= n3; i ++) { k = 0; for(int j = 1; j <= n2; j ++) { if(b[j] > c[i])++k; cnt[i][j][3][2] = k; } k = 0; for(int j = 1; j <= n1; j ++) { if(a[j] > c[i])++k; cnt[i][j][3][1] = k; } } for(int i = 0; i <= n1; i ++)for(int j = 0; j <= n2; j ++)for(int l = 0; l <= n3; l ++) dp[i][j][l][1] = dp[i][j][l][2] = dp[i][j][l][3] = mod; dp[0][0][0][1] = dp[0][0][0][2] = dp[0][0][0][3] = 0; //cout << n1 <<" "<<n2<<" "<<n3<<'\n'; for(int i = 0; i <= n1; i ++) { for(int j = 0; j <= n2; j ++) { for(int l = 0; l <= n3; l ++) { if(i == 0 && j == 0 && l == 0)continue; if(i != 0)dp[i][j][l][1] = min(dp[i-1][j][l][2], dp[i-1][j][l][3]) + cnt[i][j][1][2] + cnt[i][l][1][3]; if(j != 0)dp[i][j][l][2] = min(dp[i][j-1][l][1], dp[i][j-1][l][3]) + cnt[j][i][2][1] + cnt[j][l][2][3]; if(l != 0)dp[i][j][l][3] = min(dp[i][j][l-1][1], dp[i][j][l-1][2]) + cnt[l][j][3][2] + cnt[l][i][3][1]; } } } ans = min(min(dp[n1][n2][n3][1], dp[n1][n2][n3][2]), dp[n1][n2][n3][3]); if(ans >= mod)ans = -1; cout << ans; } int main() { if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int ntest; ntest = 1; //cin >> ntest; while(ntest -- > 0) sol(); }

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:94:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |        freopen(task".inp", "r", stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:95:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |        freopen(task".out", "w", stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...