Submission #1276937

#TimeUsernameProblemLanguageResultExecution timeMemory
1276937minhvule여별 열쇠 (JOI15_keys)C++20
0 / 100
1 ms568 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define task "task" #define fi first #define se second #define pb push_back #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i ++) #define FORD(i, a, b) for(int i = (a), _b = (b); i >= _b; i --) #define bit(x, i) ((x >> i) & 1) #define oo 1e18 #define all(v) v.begin(), v.end() using ll = long long; using pii = pair<int, int>; using vi = vector<int>; // mt19937 rd(chrono::steady_clock::now().time_since_epoch().count()); // ll rand(ll l, ll r) { assert(l <= r); return uniform_int_distribution<ll>(l, r)(rd); } const int N = 2e3 + 5; const int mod = 1e9 + 7; const int base = 31; int n, m, k, dp[N][N][2], val[N], ans = 0, sz[N], f[N]; vector<pii> g[N]; vector<pii> v; bool vis[N]; void dfs(int u, int p){ sz[u] = vis[u] = 1; dp[u][1][1] = val[u]; for(auto [v, w] : g[u]) if(v != p){ dfs(v, u); FORD(i, sz[u], 0) FOR(j, 1, min(sz[v], k - i)){ dp[u][i + j][0] = max(dp[u][i + j][0], dp[u][i][0] + max(dp[v][j][0], dp[v][j][1])); if(i > 0) dp[u][i + j][1] = max({dp[u][i + j][1], dp[u][i][1] + dp[v][j][0], dp[u][i][1] + dp[v][j][1] + w}); } sz[u] += sz[v]; } } void solve(){ cin>>n>>m>>k; FOR(i, 1, n){ int x, y; cin>>x>>y; v.pb({x, i}); v.pb({y, -i}); } sort(v.begin(), v.end()); FOR(i, 1, v.size() - 1){ int len = v[i].fi - v[i - 1].fi; if(v[i - 1].se > 0 && v[i].se > 0) val[v[i - 1].se] += len; if(v[i - 1].se < 0 && v[i].se < 0) val[-v[i].se] += len; if(v[i - 1].se > 0 && v[i].se < 0){ int x = -v[i].se, y = v[i - 1].se; if(x == y){ val[v[i].se] += len; continue; } g[x].pb({y, len}); g[y].pb({x, len}); } if(v[i - 1].se < 0 && v[i].se > 0) ans += len; } FOR(i, 1, n) if(!vis[i]){ dfs(i, 0); FORD(j, k, 0) FOR(o, 1, sz[i]) f[j + o] = max(f[j + o], f[j] + max(dp[i][o][0], dp[i][o][1])); } cout<<ans + f[k] + m - v[v.size() - 1].fi + v[0].fi; } signed main(){ ios::sync_with_stdio(false); cin.tie(NULL); if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } int nTest = 1; // cin>>nTest; while(nTest --) solve(); // cerr << "\nTime: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n"; return 0; } /* */

Compilation message (stderr)

keys.cpp: In function 'int main()':
keys.cpp:76:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
keys.cpp:77:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...