結果
問題 |
No.2701 A cans -> B cans
|
ユーザー |
|
提出日時 | 2024-03-29 21:35:20 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,148 bytes |
コンパイル時間 | 19,134 ms |
コンパイル使用メモリ | 352,044 KB |
最終ジャッジ日時 | 2025-02-20 14:50:31 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 23 WA * 50 |
ソースコード
#include<bits/stdc++.h> #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") using namespace std; using ll=long long; using ld=long double; using ull=unsigned long long; using i128 = __int128_t; #define vs vector<string> #define rep(i,n) for(int i=0;i<int(n);i++) #define rep2(i,n) for(int i=n-1;i>=0;i--) #define rep3(i,a,b) for(ll i=a;i<=ll(b);i++) #define rep4(i,a,b) for(ll i=a;i>=ll(b);i--) #define forv(i,V) for(const auto& i:V) #define all(x) x.begin(),x.end() #define fi first #define se second #define SIZE(x) int(x.size()) constexpr ll mod=998244353; //constexpr ll mod=1000000007; #define pi 3.14159265358979323 #define INF32 2147483647 #define INF64 9223372036854775807 #define faster ios::sync_with_stdio(false);std::cin.tie(nullptr) #define pii pair<int, int> #define pll pair<ll, ll> #define pb push_back #define eb emplace_back #define mp make_pair #define rev reverse #define vi vector<int> #define vll vector<ll> #define vpi vector<pair<int,int>> #define vpll vector<pair<ll,ll>> #define vvi vector<vector<int>> #define vvll vector<vector<ll>> #define prq priority_queue #define lb lower_bound #define ub upper_bound #define popcnt __builtin_popcountll #define TLE while(true); #define RE assert(false); #define MLE vector<vector<vector<long long>>> mle_mle(400,vector<vector<long long>>(1000,vector<long long>(1000))); const string YESNO[2] = {"NO", "YES"}; const string YesNo[2] = {"No", "Yes"}; const string yesno[2] = {"no", "yes"}; #define rall(n) (n).rbegin(),(n).rend() #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__) template<typename T,typename U> ostream &operator<<(ostream&os,const pair<T,U>&p){os<<p.first<<" "<<p.second;return os;} template<typename T,typename U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;} template<typename T> ostream &operator<<(ostream&os,const vector<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;} template<typename T> istream &operator>>(istream&is,vector<T>&v){for(T &in:v){is>>in;}return is;} 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);} ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max((ll)b,a);} ll min(int a,ll b){return min((ll)a,b);} ll min(ll a,int b){return min((ll)b,a);} //a以上b以下の個数 template<typename T> ll RangeOK(ll a,ll b,vector<T> &v){ return max(ub(all(v),b)-lb(all(v),a),0); } template <typename T> vector<T> compress(vector<T> &X) { vector<T> vals = X; sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); for (int i = 0; i < (int)X.size(); i++) { X[i] = lower_bound(vals.begin(), vals.end(), X[i]) - vals.begin(); } return vals; } #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #include<atcoder/all> using namespace atcoder; using mint = modint998244353; int main(){ INT(n, m); vvll v(n, vll(3)); scan(v); vvll ret(n); rep(i, n){ vll d(m+1); rep3(j, 1, m){ if(j >= v[i][0]){ d[j] = d[j-v[i][0]+v[i][1]]+v[i][2]*v[i][0]; }else{ d[j] = d[j-1]+v[i][2]; } } rep(j, m+1) d[j] -= j*v[i][2]; ret[i] = d; } sort(all(ret)); rev(all(ret)); vll nw(n); ll ans = 0; rep(i, m){ ll ma_in = 0; rep(j, n){ ll x = ret[j][nw[j]+1]-ret[j][nw[j]]; ll y = ret[ma_in][nw[ma_in]+1]-ret[ma_in][nw[ma_in]]; if(x > y){ ma_in = j; } } ans += ret[ma_in][nw[ma_in]+1]-ret[ma_in][nw[ma_in]]; nw[ma_in]++; print(ans); } }