Submission #881587

#	Time	Username	Problem	Language	Result	Execution time	Memory
881587		tsumondai	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	76 ms	269064 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME  (1.0 * clock() / CLOCKS_PER_SEC)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 4e2 + 5;
 
const int oo = 1e18, mod = 1e9 + 7;
 
int n, p[N][3], dp[N][N][N][3];
string s;
vector<int> r,g,y;

void process() {
	cin >> n;
	cin >> s;
	s=' ' + s;
	foru(i,1,n) {
		if (s[i]=='R') r.pb(i);
		if (s[i]=='G') g.pb(i);
		if (s[i]=='Y') y.pb(i);
		p[i][0] = r.size();
        p[i][1] = g.size();
        p[i][2] = y.size();
	}

	foru(i,0,r.size()) foru(j,0,g.size()) foru(k,0,y.size()) {
        if(!i && !j && !k) continue;
 
        for(int l=0;l<3;l++) dp[i][j][k][l] = oo;
 
        int u = i+j+k;
        if(i) dp[i][j][k][0] = min(dp[i-1][j][k][1], dp[i-1][j][k][2]) + ((r[i-1] + max(0ll, j-p[r[i-1]][1]) + max(0ll, k-p[r[i-1]][2])) - u);
        if(j) dp[i][j][k][1] = min(dp[i][j-1][k][0], dp[i][j-1][k][2]) + ((g[j-1] + max(0ll, i-p[g[j-1]][0]) + max(0ll, k-p[g[j-1]][2])) - u);
        if(k) dp[i][j][k][2] = min(dp[i][j][k-1][0], dp[i][j][k-1][1]) + ((y[k-1] + max(0ll, i-p[y[k-1]][0]) + max(0ll, j-p[y[k-1]][1])) - u);
    }

    int ans = *min_element(dp[r.size()][g.size()][y.size()], dp[r.size()][g.size()][y.size()]+3);
    cout << (ans >= oo ? -1 : ans);
    return;
}

signed main() {
    cin.tie(0)->sync_with_stdio(false);
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    process();
    cerr << "Time elapsed: " << __TIME << " s.\n";
    return 0;
}

/*
Xét các trường hợp đặc biệt
Kiểm tra lại input/output
Cố gắng trâu
Lật ngược bài toán
Keep calm and get VOI 
Flow:

*/

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'void process()':
joi2019_ho_t3.cpp:9:40: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define foru(i, l, r) for(int i = l; i <= r; i++)
......
   38 |  foru(i,0,r.size()) foru(j,0,g.size()) foru(k,0,y.size()) {
      |       ~~~~~~~~~~~~                      
joi2019_ho_t3.cpp:38:2: note: in expansion of macro 'foru'
   38 |  foru(i,0,r.size()) foru(j,0,g.size()) foru(k,0,y.size()) {
      |  ^~~~
joi2019_ho_t3.cpp:9:40: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define foru(i, l, r) for(int i = l; i <= r; i++)
......
   38 |  foru(i,0,r.size()) foru(j,0,g.size()) foru(k,0,y.size()) {
      |                          ~~~~~~~~~~~~   
joi2019_ho_t3.cpp:38:21: note: in expansion of macro 'foru'
   38 |  foru(i,0,r.size()) foru(j,0,g.size()) foru(k,0,y.size()) {
      |                     ^~~~
joi2019_ho_t3.cpp:9:40: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define foru(i, l, r) for(int i = l; i <= r; i++)
......
   38 |  foru(i,0,r.size()) foru(j,0,g.size()) foru(k,0,y.size()) {
      |                                             ~~~~~~~~~~~~
joi2019_ho_t3.cpp:38:40: note: in expansion of macro 'foru'
   38 |  foru(i,0,r.size()) foru(j,0,g.size()) foru(k,0,y.size()) {
      |                                        ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 55 / 55
• Subtask 3: 15 / 15
• Subtask 4: 25 / 25