Submission #704067

#	Time	Username	Problem	Language	Result	Execution time	Memory
704067		WeIlIaN	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	69 ms	162812 KiB

joi2019_ho_t3

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <climits>
using namespace std;

#define MOD 1000000007
#define fir first
#define sec second

#define push_f push_front
#define push_b push_back
#define pop_f pop_front
#define pop_b pop_back
#define mp make_pair

#define FOR(i, s, e, p) for(int i = s; i < e; i += p)
#define REP(i, n) FOR(i, 0, n, 1)

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
typedef vector<vc> vvc;
typedef vector<vpii> vvpii;
typedef queue<int> qi;
typedef queue<ll> qll;
typedef queue<pii> qpii;
typedef queue<pll> qpll;
typedef deque<int> dqi;
typedef deque<ll> dqll;
typedef deque<pii> dqpii;
typedef deque<pll> dqpll;
typedef priority_queue<int> pqi;
typedef priority_queue<ll> pqll;
typedef priority_queue<pii> pqpii;
typedef priority_queue<pll> pqpll;
typedef priority_queue<int, vi, greater<int> > r_pqi;
typedef priority_queue<ll, vll, greater<ll> > r_pqll;
typedef priority_queue<pii, vpii, greater<pii> > r_pqpii;
typedef priority_queue<pll, vpll, greater<pll> > r_pqpll;
 
const int INF = 1e9;
int dp[444][444][444][3], len[444][3];
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    string s;
    cin >> n >> s;
    vector<int> r, g, y;
    REP(i, n) {
        if(s[i] == 'R') r.push_back(i);
        if(s[i] == 'G') g.push_back(i);
        if(s[i] == 'Y') y.push_back(i);
        len[i][0] = r.size();
        len[i][1] = g.size();
        len[i][2] = y.size();
    }
    //dp[i][j][k][x] means operations needed to achieve the first i+j+k elements contain i 'R', j 'G', and k 'Y' and the last element is x
    REP(i, r.size()+1)
        REP(j, g.size()+1)
            REP(k, y.size()+1) {
                if(!i && !j && !k) {
                    REP(l, 3) dp[0][0][0][l] = 0;
                }
                else {
                    REP(l, 3) dp[i][j][k][l] = INF;
                }
                int sum = 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]+1 + max(0, j-len[r[i-1]][1]) + max(0, k-len[r[i-1]][2]) - sum);
                }
                if(j) {
                  	dp[i][j][k][1] = min(dp[i][j-1][k][0], dp[i][j-1][k][2]) + (g[j-1]+1 + max(0, i-len[g[j-1]][0]) + max(0, k-len[g[j-1]][2]) - sum);
                }
                if(k) {
                  	dp[i][j][k][2] = min(dp[i][j][k-1][0], dp[i][j][k-1][1]) + (y[k-1]+1 + max(0, i-len[y[k-1]][0]) + max(0, j-len[y[k-1]][1]) - sum);
                }
    }
    int ans = INF;
    REP(i, 3) {
        ans = min(ans, dp[r.size()][g.size()][y.size()][i]);
    }
    cout << (ans >= INF ? -1 : ans);
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:23:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 | #define FOR(i, s, e, p) for(int i = s; i < e; i += p)
      |                                          ^
joi2019_ho_t3.cpp:24:19: note: in expansion of macro 'FOR'
   24 | #define REP(i, n) FOR(i, 0, n, 1)
      |                   ^~~
joi2019_ho_t3.cpp:78:5: note: in expansion of macro 'REP'
   78 |     REP(i, r.size()+1)
      |     ^~~
joi2019_ho_t3.cpp:23:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 | #define FOR(i, s, e, p) for(int i = s; i < e; i += p)
      |                                          ^
joi2019_ho_t3.cpp:24:19: note: in expansion of macro 'FOR'
   24 | #define REP(i, n) FOR(i, 0, n, 1)
      |                   ^~~
joi2019_ho_t3.cpp:79:9: note: in expansion of macro 'REP'
   79 |         REP(j, g.size()+1)
      |         ^~~
joi2019_ho_t3.cpp:23:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 | #define FOR(i, s, e, p) for(int i = s; i < e; i += p)
      |                                          ^
joi2019_ho_t3.cpp:24:19: note: in expansion of macro 'FOR'
   24 | #define REP(i, n) FOR(i, 0, n, 1)
      |                   ^~~
joi2019_ho_t3.cpp:80:13: note: in expansion of macro 'REP'
   80 |             REP(k, y.size()+1) {
      |             ^~~

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