結果
問題 | No.1536 仕切り直し |
ユーザー | yuto1115 |
提出日時 | 2021-06-06 19:22:13 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 53 ms / 2,000 ms |
コード長 | 5,086 bytes |
コンパイル時間 | 2,272 ms |
コンパイル使用メモリ | 208,640 KB |
実行使用メモリ | 64,128 KB |
最終ジャッジ日時 | 2024-05-04 00:50:29 |
合計ジャッジ時間 | 3,042 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 6 ms
9,600 KB |
testcase_04 | AC | 19 ms
25,600 KB |
testcase_05 | AC | 34 ms
45,824 KB |
testcase_06 | AC | 9 ms
13,440 KB |
testcase_07 | AC | 8 ms
12,544 KB |
testcase_08 | AC | 19 ms
27,520 KB |
testcase_09 | AC | 23 ms
32,000 KB |
testcase_10 | AC | 53 ms
64,128 KB |
testcase_11 | AC | 14 ms
20,352 KB |
testcase_12 | AC | 38 ms
49,408 KB |
コンパイルメッセージ
main.cpp: In function 'int main()': main.cpp:183:14: warning: 'j' may be used uninitialized [-Wmaybe-uninitialized] 183 | while (i or j) { | ~~^~~~ main.cpp:177:9: note: 'j' was declared here 177 | int j; | ^
ソースコード
#include<bits/stdc++.h> #define overload4(_1, _2, _3, _4, name, ...) name #define rep1(i, n) for (ll i = 0; i < ll(n); ++i) #define rep2(i, s, n) for (ll i = ll(s); i < ll(n); ++i) #define rep3(i, s, n, d) for(ll i = ll(s); i < ll(n); i+=d) #define rep(...) overload4(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__) #define rrep1(i, n) for (ll i = ll(n)-1; i >= 0; i--) #define rrep2(i, n, t) for (ll i = ll(n)-1; i >= (ll)t; i--) #define rrep3(i, n, t, d) for (ll i = ll(n)-1; i >= (ll)t; i-=d) #define rrep(...) overload4(__VA_ARGS__,rrep3,rrep2,rrep1)(__VA_ARGS__) #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define SUM(a) accumulate(all(a),0LL) #define MIN(a) *min_element(all(a)) #define MAX(a) *max_element(all(a)) #define popcount(x) __builtin_popcountll(x) #define pb push_back #define eb emplace_back #ifdef __LOCAL #define debug(...) { cout << #__VA_ARGS__; cout << ": "; print(__VA_ARGS__); cout << flush; } #else #define debug(...) void(0) #endif #define INT(...) int __VA_ARGS__;scan(__VA_ARGS__) #define LL(...) ll __VA_ARGS__;scan(__VA_ARGS__) #define STR(...) string __VA_ARGS__;scan(__VA_ARGS__) #define CHR(...) char __VA_ARGS__;scan(__VA_ARGS__) #define DBL(...) double __VA_ARGS__;scan(__VA_ARGS__) #define LD(...) ld __VA_ARGS__;scan(__VA_ARGS__) using namespace std; using ll = long long; using ld = long double; using P = pair<int, int>; using LP = pair<ll, ll>; using vi = vector<int>; using vvi = vector<vi>; using vl = vector<ll>; using vvl = vector<vl>; using vd = vector<double>; using vvd = vector<vd>; using vs = vector<string>; using vc = vector<char>; using vvc = vector<vc>; using vb = vector<bool>; using vvb = vector<vb>; using vp = vector<P>; using vvp = vector<vp>; template<class S, class T> istream &operator>>(istream &is, pair<S, T> &p) { return is >> p.first >> p.second; } template<class S, class T> ostream &operator<<(ostream &os, const pair<S, T> &p) { return os << '{' << p.first << ", " << p.second << '}'; } template<class S, class T, class U> istream &operator>>(istream &is, tuple<S, T, U> &t) { return is >> get<0>(t) >> get<1>(t) >> get<2>(t); } template<class S, class T, class U> ostream &operator<<(ostream &os, const tuple<S, T, U> &t) { return os << '{' << get<0>(t) << ", " << get<1>(t) << ", " << get<2>(t) << '}'; } template<class T> istream &operator>>(istream &is, vector<T> &v) { for (T &t:v) { is >> t; } return is; } template<class T> ostream &operator<<(ostream &os, const vector<T> &v) { os << '['; rep(i, v.size())os << v[i] << (i == int(v.size() - 1) ? "" : ", "); return os << ']'; } template<class T> void vecout(const vector<T> &v, char div = '\n') { rep(i, v.size()) cout << v[i] << (i == int(v.size() - 1) ? '\n' : div); } template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } void scan() {} template<class Head, class... Tail> void scan(Head &head, Tail &... tail) { cin >> head; scan(tail...); } template<class T> void print(const T &t) { cout << t << '\n'; } template<class Head, class... Tail> void print(const Head &head, const Tail &... tail) { cout << head << ' '; print(tail...); } template<class... T> void fin(const T &... a) { print(a...); exit(0); } struct Init_io { Init_io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cout << boolalpha << fixed << setprecision(15); cerr << boolalpha << fixed << setprecision(15); } } init_io; const string yes[] = {"no", "yes"}; const string Yes[] = {"No", "Yes"}; const string YES[] = {"NO", "YES"}; const int inf = 1001001001; const ll linf = 1001001001001001001; vvi graph(int n, int m, bool directed = false, int origin = 1) { vvi G(n); rep(_, m) { INT(u, v); u -= origin, v -= origin; G[u].pb(v); if (!directed) G[v].pb(u); } return G; } template<class T> vector<vector<pair<int, T>>> weighted_graph(int n, int m, bool directed = false, int origin = 1) { vector<vector<pair<int, T>>> G(n); rep(_, m) { int u, v; T w; scan(u, v, w); u -= origin, v -= origin; G[u].eb(v, w); if (!directed) G[v].eb(u, w); } return G; } ll dp[2010][2010]; P pre[2010][2010]; int main() { INT(n, m); vi a(n); cin >> a; rep(i, n + 1) rep(j, m + 1) dp[i][j] = -linf; dp[0][0] = 0; rep(i, n) rep(j, m + 1) { if (chmax(dp[i][j + 1], dp[i][j])) pre[i][j + 1] = {i, j}; if (chmax(dp[i + 1][j], dp[i][j] + (j & 1 ? -a[i] : a[i]))) pre[i + 1][j] = {i, j}; } ll mx = -linf; int j; rep(i, m + 1) if (chmax(mx, dp[n][i])) j = i; int i = n; debug(i, j); vi ans; rep(_, m - j) ans.pb(n); while (i or j) { debug(i, j); auto[ni, nj] = pre[i][j]; if (nj != j) ans.pb(i); i = ni, j = nj; } vecout(ans); }