제출 #320710

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
320710		caoash	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	103 ms	163048 KiB

joi2019_ho_t3

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

using ll = long long;

using vi = vector<int>;
using vl = vector<ll>;
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define lb lower_bound
#define ub upper_bound

using pi = pair<int,int>;
#define f first
#define s second
#define mp make_pair

namespace output {
  void pr(int x) {
    cout << x;
  }
  void pr(long x) {
    cout << x;
  }
  void pr(ll x) {
    cout << x;
  }
  void pr(unsigned x) {
    cout << x;
  }
  void pr(unsigned long x) {
    cout << x;
  }
  void pr(unsigned long long x) {
    cout << x;
  }
  void pr(float x) {
    cout << x;
  }
  void pr(double x) {
    cout << x;
  }
  void pr(long double x) {
    cout << x;
  }
  void pr(char x) {
    cout << x;
  }
  void pr(const char * x) {
    cout << x;
  }
  void pr(const string & x) {
    cout << x;
  }
  void pr(bool x) {
    pr(x ? "true" : "false");
  }

  template < class T1, class T2 > void pr(const pair < T1, T2 > & x);
  template < class T > void pr(const T & x);

  template < class T, class...Ts > void pr(const T & t,
    const Ts & ...ts) {
    pr(t);
    pr(ts...);
  }
  template < class T1, class T2 > void pr(const pair < T1, T2 > & x) {
    pr("{", x.f, ", ", x.s, "}");
  }
  template < class T > void pr(const T & x) {
    pr("{"); // const iterator needed for vector<bool>
    bool fst = 1;
    for (const auto & a: x) pr(!fst ? ", " : "", a), fst = 0;
    pr("}");
  }

  void ps() {
    pr("\n");
  } // print w/ spaces
  template < class T, class...Ts > void ps(const T & t,
    const Ts & ...ts) {
    pr(t);
    if (sizeof...(ts)) pr(" ");
    ps(ts...);
  }

  void pc() {
    cout << "]" << endl;
  } // debug w/ commas
  template < class T, class...Ts > void pc(const T & t,
    const Ts & ...ts) {
    pr(t);
    if (sizeof...(ts)) pr(", ");
    pc(ts...);
  }
  #define dbg(x...) pr("[", #x, "] = ["), pc(x);
}

#ifdef mikey 
using namespace output;
#else
using namespace output;
#define dbg(x...)
#endif

const int MX = 200005;
const int MOD = (int) (1e9 + 7);
const ll INF = (ll) 1e18;

int n;

int dp[405][405][405][3];
int pos[405][3];
int psum[405][3];

int main(){
#ifdef mikey 
    freopen("a.in", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    string s; cin >> s;
    string al = "RGY";
    int cnts[3];
    for (int i = 0; i < 3; i++) {
        pos[0][i] = -1;
        int c = 1;
        for (int j = 0; j < n; j++) {
            if (j != 0) psum[j][i] = psum[j - 1][i];
            if (s[j] == al[i]) {
                pos[c++][i] = j; 
                psum[j][i]++;
            }
        }
        cnts[i] = c - 1;
    }
    auto qry = [&] (int l, int r, int t) {
        if (r < l) return 0;
        if (l == 0) return psum[r][t];
        else return psum[r][t] - psum[l - 1][t];
    };
    for (int i = 0; i <= cnts[0]; i++) 
    for (int j = 0; j <= cnts[1]; j++) 
    for (int k = 0; k <= cnts[2]; k++) {
        dp[i][j][k][0] = 1e9;
        dp[i][j][k][1] = 1e9;
        dp[i][j][k][2] = 1e9;
    }
    dp[0][0][0][0] = 0;
    dp[0][0][0][1] = 0;
    dp[0][0][0][2] = 0;
    for (int i = 0; i <= cnts[0]; i++) {
        for (int j = 0; j <= cnts[1]; j++) {
            for (int k = 0; k <= cnts[2]; k++) {
                for (int p = 0; p < 3; p++) {
                    if (i != cnts[0] && p != 0) {
                        int add = qry(pos[j][1] + 1, pos[i + 1][0], 1) + qry(pos[k][2] + 1, pos[i + 1][0], 2);
                        dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0], dp[i][j][k][p] + add);
                    }
                    if (j != cnts[1] && p != 1) {
                        int add = qry(pos[i][0] + 1, pos[j + 1][1], 0) + qry(pos[k][2] + 1, pos[j + 1][1], 2);
                        dp[i][j + 1][k][1] = min(dp[i][j + 1][k][1], dp[i][j][k][p] + add);
                    }
                    if (k != cnts[2] && p != 2) {
                        int add = qry(pos[i][0] + 1, pos[k + 1][2], 0) + qry(pos[j][1] + 1, pos[k + 1][2], 1);
                        dp[i][j][k + 1][2] = min(dp[i][j][k + 1][2], dp[i][j][k][p] + add);
                    }
                }
            }
        }
    }
    int ans = INT_MAX;
    for (int p = 0; p < 3; p++) ans = min(ans, dp[cnts[0]][cnts[1]][cnts[2]][p]);
    if (ans == 1e9) {
        cout << -1 << '\n';
    } else {
        cout << ans << '\n';
    }
}

컴파일 시 표준 에러 (stderr) 메시지

joi2019_ho_t3.cpp:104: warning: "dbg" redefined
  104 | #define dbg(x...)
      | 
joi2019_ho_t3.cpp:97: note: this is the location of the previous definition
   97 |   #define dbg(x...) pr("[", #x, "] = ["), pc(x);
      |

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