Codeforces Round #608 (Div. 2)

A Suits standard input/output 1 s, 256 MB Submit Add to favourites x7772

　　如题意，模拟
B Blocks standard input/output 2 s, 256 MB Submit Add to favourites x5220

　　给你一个 n 长度的 BW 字符串，问是否能在 3n 次翻转内将字符串变成全 B 或者全 W，（翻转的话是相邻的两个字符都翻一下 B-W 或者 W-B），做法是以白色为标准从前到后跑一遍如果是黑色字符就翻转下这个字符和后面的字符，跑完一遍后如果还没有变成全白，那就再以黑色为标准跑一遍如果还不能变成全B 或 W 串那便无解。
C Shawarma Tent standard input/output 1 s, 256 MB Submit Add to favourites x5079

　　给你一个学校的地址x0 y0，还有 n 个学生的家庭地址，问将一个帐篷建在哪里能够有最多学生经过（学生到学校只能走最短的dx+dy），当时写的时候画了个图以学校地址为中心，猜了一波发现可以分别用 x=x0 和 y= y0 将平面划分成两个区域，如果在哪个区域的学生坐标点最多那帐篷就得建在这条路上为最优至于帐篷坐标点就为学校地址往那个区域-1即可。enmmm 过了，结束以后看题解大致如此。
D Portals standard input/output 2 s, 256 MB Submit Add to favourites x978

　　enmmmmm题意confused，结束以后看了题解再看了一遍题目大概懂了，给你 n 个城堡必须按顺序攻陷，每个城堡有攻陷需要的最少士兵数量要求和攻下来以后能够增加的士兵数量还有占领这座城堡能得到的收益，有 m 个portal u-> v 在城堡 u 通过portal可以派兵去城堡v ，至于占领城堡只需要一个士兵即可， portal只有在当前城堡u时才可以用，也就是说每个城堡需要进行一次决策，求最大的收益, 然后题解用的是二维dp dp[i][j] 表示身处 i 城堡且有 j 个士兵，转移方程为

　　if(dp[i][j] >= 0) dp[i+1][j+b[i]] = max(dp[i][j], dp[i+1][j+b[i]]);

　　如果 i 能派兵到 j dp[i+1][k-1] = max(dp[i+1][k]+c[j], dp[i+1][k-1]);

　　至于poral 初始化所有城堡为i 表示都能驻兵自己，只需要记录最大的编号能到 i 的城堡，
　　最后求下最大的 dp[n][i] 即可，代码如下

E Common Number standard input/output 2 s, 256 MB Submit Add to favourites x1312
F Divide The Students standard input/output 8 s, 512 MB Submit Add to favourites x56

#include<bits/stdc++.h>//Codeforces Round #608 (Div. 2)
using namespace std;

#define _for(i,a,b) for(int i = (a); i < (b); i++)
#define _rep(i,a,b) for(int i = (a); i <= (b); i++)
#define _per(i,a,b) for(int i = (a); i > (b); i--)
#define ll long long

void taskA(){
    int t; 
    t = 1;
    while(t--) {
        int a,b,c,d,e,f, ans = 0;
        cin >> a >> b >> c >> d >> e >> f;
        if(e < f) {
            int x = min(b, min(c, d));
            b -= x, c -= x, d-=x;
            ans += f*x;
            x = min(a, d); if(x < 0) x = 0;
            ans += e*x;
        }else {
            int x = min(a, d);
            a -= x, d-=x;
            ans += e*x;
            x = min(b, min(c, d)); 
            b -= x, c -= x, d-=x; if(x < 0) x = 0;
            ans += f*x;
        }
        cout << ans  << '
';
    }return;
}

void taskB(){
    int n; cin >> n;
    string s; cin >> s;
    int w = 0, b = 0;
    vector<int> v(n);
    for(auto &c : s) {
        if(c == 'W') w++, c = 0;
        else b++, c = 1; 
    }
    if(!w || !b) cout << "0
";
    else if(n%2==0 && b%2==1) cout << "-1
";
    else{
        vector<int> ans;
        _for(x,0,2) {
            _for(i,0,n) {
                if(s[i]==x || i==n-1) continue;
                ans.push_back(i);
                s[i] ^= 1, s[i+1]^=1;
            }
            if(x == s[n-1]) {
                    cout << ans.size() << '
';
                    //sort(v.begin(), v.end());
                    for(int x1 : ans) cout << x1+1 << " ";
                    cout << '
';
                    return;
            }
        } 
    }return;
}

void taskC(){
    int n; cin >> n; int x0,y0; cin>> x0 >> y0;
    vector<int> x(n), y(n);
    int x1 = 0, x2 = 0, y1 = 0,y2 = 0;
    _for(i,0,n) {
        cin >> x[i] >> y[i];
        if(x[i] > x0) x1++;
        else if(x[i] < x0) x2++;
        if(y[i] > y0) y1++;
        else if(y[i] <  y0) y2++;
    }
    int ma = max(x1, max(x2, max(y1, y2)));
    if(ma == x1) cout << x1 << '
' << x0+1 << ' ' << y0;
    else if(ma == x2) cout << x2 << '
' << x0-1 << ' ' << y0;
    else if(ma == y2) cout << y2 << '
' << x0 << ' ' << y0-1;
    else if(ma == y1) cout << y1 << '
' << x0 << ' ' << y0+1;
    return;
}

void taskC1(){
    int n; cin >> n; int x0,y0; cin >> x0 >> y0;
    int dx[] = {0,0,-1,1}, dy[] = {-1,1,0,0}, d[5] = {};
    _for(i,0,n) {
        int x,y; cin >> x >> y;
        _for(j,0,4) {
            int x1 = x0+dx[j], y1 = y0+dy[j];
            if(abs(x-x1)+abs(y-y1)+abs(x1-x0)+abs(y1-y0) == abs(x-x0)+abs(y-y0)) d[j]++;
        }
    }
    int gol = 0;
    _for(i,1,4) if(d[i] > d[gol]) gol = i;

    cout << d[gol] << '
';
    cout << x0+dx[gol] << " " << y0+dy[gol] << '
';
    return;
}

int dp[5005][5005];
void taskD(){
    int n,m,K;
    cin >> n >> m >> K;
    vector<int> a(n), b(n), c(n);
    ll sum = 0;

    vector<int> latest(n);
    _for(i,0,n) cin >> a[i] >> b[i] >> c[i], latest[i] = i;
    
    _for(i,0,m) {
        int x,y; cin >> x >> y;
        x--, y--; latest[y] = max(latest[y], x);
    }
    _for(i,0,5005) _for(j,0,5005) dp[i][j] = -1e9;

    dp[0][K] = 0;
    _for(i,0,n) {
        _for(j,a[i],5005) {
            if(dp[i][j] >= 0) 
                dp[i+1][j+b[i]] = max(dp[i][j], dp[i+1][j+b[i]]);
        }

        _rep(j,0,i) {
            if(latest[j] == i)
                _for(k,1,5005) if(dp[i+1][k] >= 0)
                    dp[i+1][k-1] = max(dp[i+1][k]+c[j], dp[i+1][k-1]);
        }
    }

    int ans = -1;
    _for(i,0,5005) ans = max(ans, dp[n][i]);
    cout << ans << '
';
    return;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    //freopen("output.txt", "w", stdout);
    //taskA();
    //taskB();
    //taskC();
    taskD();
    return 0;
}