Submission #62075948

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
Start: 
End: 
Time used: 
「責任を負う人の話は、あなたと話したことがありますよね」 
「当時の私はまだわからないけど……今は理解できるようになった」 
「大人としての責務。そして、その延長線上にある、あなたの選択」 
「それに代表されるアイデアもあります」 
「だから、先生」 
「信じられる大人のあなたなら、この歪んだ変形の終点とは、違う結果……そこにつながる選択肢……きっとあなたは見つけることができます」
DON'T GET STUCK ON ONE APPROACH!!!
*/
#include <bits/stdc++.h>//喵内～
#define re register//喵内～
#define rep(i,a,b) for (re int i = (a);i <= (b); ++i)
#define debug(x) cout << #x << '=',print(x),putchar(' ')
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
#define pi pair<int,int>
#define mp(a,b) make_pair(a,b)
typedef long long ll;
using namespace std;//喵内～
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

/*
Start: 
End: 
Time used: 
「責任を負う人の話は、あなたと話したことがありますよね」 
「当時の私はまだわからないけど……今は理解できるようになった」 
「大人としての責務。そして、その延長線上にある、あなたの選択」 
「それに代表されるアイデアもあります」 
「だから、先生」 
「信じられる大人のあなたなら、この歪んだ変形の終点とは、違う結果……そこにつながる選択肢……きっとあなたは見つけることができます」
DON'T GET STUCK ON ONE APPROACH!!!
*/
#include <bits/stdc++.h>//喵内～
#define re register//喵内～
#define rep(i,a,b) for (re int i = (a);i <= (b); ++i)
#define debug(x) cout << #x << '=',print(x),putchar(' ')
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
#define pi pair<int,int>
#define mp(a,b) make_pair(a,b)
typedef long long ll;
using namespace std;//喵内～
inline ll read(){
    ll s = 0,f = 1;char c = getchar();
    while (!isdigit(c)){if (c == '-')f = -1;c = getchar();}
    while (isdigit(c)){s = (s<<3) + (s<<1) + (c ^ 48);c = getchar();}
    return s * f;
}//喵内～
void print(__int128 x){if (x < 0) {putchar('-'),print(-x);return ;}if (x >= 10) print(x / 10);putchar(x % 10 + 48);}//喵内～
const int Mod = 1e9 + 7;//喵内～要填数字哟～
//const int Mod = 998244353;//喵内～要填数字哟～
const ll INF = 0x3f3f3f3f;
const int N = 5005;//喵内～要填数字哟～
ll qpow(ll x,ll y){
   ll res = 1;
    for (;y;y >>= 1,x = x * x % Mod) if (y & 1) res = res * x % Mod;
    return res;
}
//ATTENTION IS ALL YOU NEED
int n,x;
int f[3][N];//编号为 i 的维生素，用 N 个空间可以拿到最多 f[i][N] 的维生素。
int check(int val){
    if (f[0][x] < val || f[1][x] < val || f[2][x] < val) return 0;
    int siz0 = lower_bound(f[0],f[0] + x + 1,val) - f[0];
    int siz1 = lower_bound(f[1],f[1] + x + 1,val) - f[1];
    int siz2 = lower_bound(f[2],f[2] + x + 1,val) - f[2];
    return siz0 + siz1 + siz2 <= x;
}
signed main(){
    n = read(),x = read();
    for (int i = 1;i <= n;++i){
        int v = read(),a = read(),c = read(); --v;
        for (int j = x;j >= c;--j)
            f[v][j] = max(f[v][j],f[v][j - c] + a);
    }
    int l = 0,r = 1e9,ans = 0;
    while (l <= r){
        int mid = l + r >> 1;
        if (check(mid)) l = mid + 1,ans = mid;
        else r = mid - 1;
    } cout << ans << endl;
    return 0;
}//喵内～
/*
What's wrong with my code?
1. 小数据？特殊数据？如 n = 1?
2. 最小值，最大值取多少？是否会溢出？
3. 初始值有没有赋值？有没有建树？
4. 数组大小？是否越界？
5. 思考暴力的时候，考虑是否可能是多个连续段？或者是个数不确定无法暴力？
6. 进行详细的分类讨论?
7. 选择的区间是否可以为空？

Trick:
1. 连通 通常带有特殊性质
2. LIS 有另一种求法
3. Brovuka?

About implementation skills:
1. 全局变量多用长变量名，而局部变量，临时变量，和函数传递的参数使用短变量名。
2. 大模拟尽量遵循：怎么方便怎么写。
3. 对于一些数据很小的需要维护的量并且需要大量讨论时，可以考虑把数组拆掉换成变量。
4. 写成多个函数。
*/

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:57:21: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   57 |         int mid = l + r >> 1;
      |                   ~~^~~

Judge Result