Submission #1281923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281923		Kerim	Colouring a rectangle (eJOI19_colouring)	C++20	0 / 100	2 ms	572 KiB

colouring

#include "bits/stdc++.h"

using namespace std;
const int N = 4004;
int d, n, m;
int a[N], b[N];
vector<pair<pair<int,int>,int > > intervals;
long long cost[N];
long long rec(int pos, int rp, vector<vector<long long>>&dp){
    if (pos == intervals.size())
        return 0;
    long long &ret=dp[pos][rp];
    if (~ret)
        return ret;
    int a_value = intervals[pos].second;
    int l = intervals[pos].first.first;
    int r = intervals[pos].first.second;
    ret = rec(pos+1, rp, dp) + a_value;
    ret = min(ret, rec(pos+1, max(rp, r), dp) + cost[max(rp, r)] - cost[rp]);
    return ret;
} 


// 0: a[i]
// 1: interval used [l, r]
// dp[i][0/1]

// dp[i][0] = min(dp[i-1][0], dp[i-1][1]) + a[i]
// dp[i][1] = min(dp[i-1][0]+ sumB(l[i], r[i]),
//              dp[j][1] + sumB(r[j], r[i]) + 
//              sumA(j+1, i-1)) 

// - r[j] <= r[i]
//  dp[j][1] + sumB[r[i]]-sumB[r[j]] + sumA[i-1] - sumA[j]
// - else
//  dp[j][1] + sumA[i-1] - sumA[j]

// - r[j] <= r[i]
//  dp[i][1] = min(find(1, r[i]) + sumB[r[i]] + sumA[i-1])//find i
//  upd(r[i], dp[i][1] - sumB[r[i]] - sumA[i]) //update, j

// - else
//  dp[i][1] = min(find(r[i]+1, N) + sumA[i-1])//find i
//  upd(r[i], dp[i][1] - sumA[i]) //update, j


long long solve(){
    // for (int i = 0; i < intervals.size(); i++){
    //     cout<<intervals[i].first.first<<" "<<intervals[i].first.second<<endl;
    // }
    sort(intervals.begin(), intervals.end());
    for (int i = 1; i <= d; i++)
        cost[i] += cost[i-1];
    vector<vector<long long> >dp(intervals.size(), vector<long long>(d+1, -1));
    return rec(0, 0, dp);
}
int f(int x, int y){
    return x + y - 1;
}
int main(){
    // freopen("file.in", "r", stdin);
    scanf("%d%d", &n, &m);
    d = n+m-1;
    for (int i = 1; i <= d; i++)
        scanf("%d", a+i);
    reverse(a+1, a+d+1);
    for (int i = 1; i <= d; i++)
        scanf("%d", b+i);
    for (int i = 1; i <= d; i+=2){
        int x, y, xp, yp;
        if (i <= n)
            x = n-i+1, y = 1;
        else
            x = 1, y = i-n+1;
        int k = min(n-x, m-y);
        xp = x+k; yp = y+k;
        intervals.push_back({{f(x, y), f(xp, yp)}, a[i]});
    }

    for(int i = 1; i <= d; i++){
        if (i%2 == n%2)
            cost[i] = b[i];
        else
            cost[i] = 0;
    }
    long long answer = solve();

    intervals.clear(); 
    for (int i = 2; i <= d; i+=2){
        int x, y, xp, yp;
        if (i <= n)
            x = n-i+1, y = 1;
        else
            x = 1, y = i-n+1;
        int k = min(n-x, m-y);
        xp = x+k; yp = y+k;
        intervals.push_back({{f(x, y), f(xp, yp)}, a[i]});
    }

    for(int i = 1; i <= d; i++){
        if (i%2 != n%2)
            cost[i] = b[i];
        else
            cost[i] = 0;
    }
    answer += solve();



    printf("%lld\n", answer);
}   

Compilation message (stderr)

colouring.cpp: In function 'int main()':
colouring.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
colouring.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         scanf("%d", a+i);
      |         ~~~~~^~~~~~~~~~~
colouring.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         scanf("%d", b+i);
      |         ~~~~~^~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 10
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20