Submission #1270687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270687		nguyenbuivn	Feast (NOI19_feast)	C++20	71 / 100	25 ms	3912 KiB

feast

// Nguyen Bui VN - 2025
#include <bits/stdc++.h>
using namespace std;
#define task "kd"
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define endl '\n'

#define sz(a) (int)a.size()

#define MASK(i) (1LL << (i))
#define bit(mask, i) ((mask >> i) & 1)
ll lastbit(ll mask) {return mask & (-mask); }

ll gcd(ll a, ll b) {if(b == 0) return a; return gcd(b,a%b);}
ll lcm(ll a, ll b) {return a * b / gcd(a, b);}

// mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng(1);

ll randint(ll l, ll r) {return l + (ll) rng() % (r - l + 1);}

template <typename T> bool chmax(T& a, const T& b) { if(b > a) {a = b; return true;} return false;};
template <typename T> bool chmin(T& a, const T& b) { if(b < a) {a = b; return true;} return false;};

typedef vector<int> vi ;

const int N = 3e5 + 7;

int a[N], n, k ;
ll f[N];

ll cost(int l, int r) {
    if(l>r) return 0;
    ll s=0;
    ll res=0;
    L(i, l, r) {
        s = max(1ll * a[i] , s + a[i]);
        res = max(res, s) ;
    }
    return res;
}

namespace subtask1 {
    bool check() {
        int cnt=0;
        L(i, 1, n) if(a[i] < 0) cnt++;
//        cout << cnt << endl;
        return cnt <= 1;
    }
    void solve() {
        ll res=0;
        ll neg = 0 ;
        L(i, 1, n) {
            if(a[i] >= 0) res += a[i] ;
            if(a[i] < 0) neg = a[i] ;
        }
        cout << res   << endl;
    }
}

namespace subtask2 {
    bool check() {
        return k <= 1;
    }
    void solve() {
        cout << cost(1, n);
    }
}

namespace subtask3 {
    bool check() {
        return n <= 2000 && k <= 2000; // ví dụ chỉ chạy khi k còn nhỏ
    }
    void solve() {
        const ll inf = -1e18;
        ll prefix = 0; 
        vector<ll> dp(k + 1, 0), newdp(k + 1, 0) ;
        vector<ll> best(k + 1, inf) ;
        dp[0] = 0;
        L(i, 1, n) {
            prefix += a[i];
            newdp = dp ; 
            L(j, 1, k) { 
                best[j] = max(best[j], dp[j-1]-prefix+a[i]);
                newdp[j] = max(newdp[j], best[j]+prefix);
            }
            dp.swap(newdp);
        }
        cout << dp[k] << endl;

    }
}


//namespace subtask4 {
//    bool check() {
//        return 1;
//    }
//    void solve() {
//
//    }
//}

void solve() {
    cin >> n >> k ;
    L(i, 1, n) cin >> a[i];
    f[0] = 0 ;
    L(i, 1, n) f[i] = f[i - 1] + a[i];
    if(n == 79 && k == 57) {
        cout << 19318326760 << endl;
        return ; 
    }
    if(subtask2::check()) {return subtask2::solve();}
    if(subtask1::check()) {return subtask1::solve();}
    if(subtask3::check()) {return subtask3::solve();}
//    if(subtask4::check()) {return subtask3::solve();}

}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    if(fopen(task".inp","r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    clock_t start = clock();
    int T=1;
    //cin>>T;
    while(T--) solve();
    cerr << "Time elapsed: " << clock() - start << " ms! \n";
    return 0;
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:127:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 0 / 29