Submission #1275192

#TimeUsernameProblemLanguageResultExecution timeMemory
1275192nanaseyuzukiGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++20
Compilation error
0 ms0 KiB
#include <bits/stdc++.h>
// Author: Kazuki_Will_Win_VOI_8703
#define fi first
#define se second
#define pii pair<int, int>
#define int long long
#define all(a) a.begin(), a.end()
using namespace std;

const int mn = 405 + 5, bm = (1 << 11) + 1, mod = 1e9 + 7, offset = 5e4, B = 320 + 5;
const int inf = 1e18, base = 311;

int n, prefix[mn][3];
string s;
vector <int> pos[mn];
int dp[405][405][405][5];

int f(int i, int j, int k, int pre){
    if(i + j + k == n) return 0;
    if(dp[i][j][k][pre] != -1) return dp[i][j][k][pre];
    dp[i][j][k][pre] = inf;
    for(int nxt = 0; nxt <= 2; nxt ++){
        if(nxt == pre) continue;
        int cost = 0;
        int p, newi, newj, newk;

        if(nxt == 0){
            if(i + 1 > pos[nxt].size() - 1) continue;
            p = pos[0][i + 1];
            newi = i + 1, newj = j, newk = k;
        }
        
        if(nxt == 1){
            if(j + 1 > pos[nxt].size() - 1) continue;
            p = pos[nxt][j + 1];
            newi = i, newj = j + 1, newk = k;
        }
        
        if(nxt == 2){
            if(k + 1 > pos[nxt].size() - 1) continue;
            p = pos[2][k + 1];
            newi = i, newj = j, newk = k + 1;
        }
        for(int col = 0; col <= 2; col ++){
            if(col == nxt) continue;
            if(col == 0) cost += max(0ll, prefix[p][col] - i);
            if(col == 1) cost += max(0ll, prefix[p][col] - j);
            if(col == 2) cost += max(0ll, prefix[p][col] - k);
        }

        dp[i][j][k][pre] = min(dp[i][j][k][pre], f(newi, newj, newk, nxt) + cost);
    }
    return dp[i][j][k][pre];
}

void solve(){
    cin >> n >> s;
    s = "#" + s;
    for(int i = 0; i <= 2; i++) pos[i].push_back(0);
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= 2; j++) prefix[i][j] = prefix[i - 1][j];
        if(s[i] == 'G'){
            prefix[i][0] ++;
            pos[0].push_back(i);
        }
        if(s[i] == 'R'){
            prefix[i][1] ++;
            pos[1].push_back(i);
        }
        if(s[i] == 'Y'){
            prefix[i][2] ++;
            pos[2].push_back(i);
        }
    }

    for(int i = 0; i <= pos[0].size() - 1; i ++){
        for(int j = 0; j <= pos[1].size() - 1; j++){
            for(int k = 0; k <= pos[2].size() - 1; k++){
                for(int pre = 0; pre <= 3; pre ++){
                    dp[i][j][k][pre] = -1;
                }
            }
        }
    }

    cout << f(0, 0, 0, 4) << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t --){
        solve();
    }
}

Compilation message (stderr)

/tmp/ccXwOttd.o: in function `__tcf_0':
joi2019_ho_t3.cpp:(.text+0x9): relocation truncated to fit: R_X86_64_PC32 against symbol `pos' defined in .bss section in /tmp/ccXwOttd.o
/tmp/ccXwOttd.o: in function `f(long long, long long, long long, long long)':
joi2019_ho_t3.cpp:(.text+0x71): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/ccXwOttd.o
joi2019_ho_t3.cpp:(.text+0xd6): relocation truncated to fit: R_X86_64_PC32 against symbol `pos' defined in .bss section in /tmp/ccXwOttd.o
joi2019_ho_t3.cpp:(.text+0xdd): relocation truncated to fit: R_X86_64_PC32 against symbol `pos' defined in .bss section in /tmp/ccXwOttd.o
joi2019_ho_t3.cpp:(.text+0x125): relocation truncated to fit: R_X86_64_PC32 against symbol `prefix' defined in .bss section in /tmp/ccXwOttd.o
joi2019_ho_t3.cpp:(.text+0x1b6): relocation truncated to fit: R_X86_64_PC32 against symbol `pos' defined in .bss section in /tmp/ccXwOttd.o
joi2019_ho_t3.cpp:(.text+0x1bd): relocation truncated to fit: R_X86_64_PC32 against symbol `pos' defined in .bss section in /tmp/ccXwOttd.o
joi2019_ho_t3.cpp:(.text+0x243): relocation truncated to fit: R_X86_64_PC32 against symbol `pos' defined in .bss section in /tmp/ccXwOttd.o
joi2019_ho_t3.cpp:(.text+0x24a): relocation truncated to fit: R_X86_64_PC32 against symbol `pos' defined in .bss section in /tmp/ccXwOttd.o
joi2019_ho_t3.cpp:(.text+0x27b): relocation truncated to fit: R_X86_64_PC32 against symbol `prefix' defined in .bss section in /tmp/ccXwOttd.o
/tmp/ccXwOttd.o: in function `solve()':
joi2019_ho_t3.cpp:(.text+0x2d9): additional relocation overflows omitted from the output
/usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(ios_init.o): in function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x1f): failed to convert GOTPCREL relocation against '_ZNSt8ios_base4Init11_S_refcountE'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x1ed): failed to convert GOTPCREL relocation against '_ZSt4cout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x252): failed to convert GOTPCREL relocation against '_ZSt3cin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x2bc): failed to convert GOTPCREL relocation against '_ZSt4cerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x316): failed to convert GOTPCREL relocation against '_ZSt4clog'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x50f): failed to convert GOTPCREL relocation against '_ZSt5wcout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x57d): failed to convert GOTPCREL relocation against '_ZSt4wcin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x5f0): failed to convert GOTPCREL relocation against '_ZSt5wcerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x654): failed to convert GOTPCREL relocation against '_ZSt5wclog'; relink with --no-relax
/usr/bin/ld: final link failed
collect2: error: ld returned 1 exit status