結果

問題 No.568 じゃんじゃん　落とす　委員会
ユーザー tactac
提出日時 2019-06-21 16:32:20
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,875 bytes
コンパイル時間 1,803 ms
コンパイル使用メモリ 178,252 KB
実行使用メモリ 12,532 KB
最終ジャッジ日時 2024-06-07 12:46:24
合計ジャッジ時間 8,509 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 29 ms
10,736 KB
testcase_01 AC 29 ms
5,376 KB
testcase_02 WA -
testcase_03 AC 3 ms
5,376 KB
testcase_04 WA -
testcase_05 TLE -
testcase_06 WA -
testcase_07 WA -
testcase_08 AC 3 ms
5,376 KB
testcase_09 TLE -
testcase_10 TLE -
testcase_11 WA -
testcase_12 TLE -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
/*
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
 */
using namespace std;
//type
typedef long long ll;
#define pii pair<int, int>
#define vi vector<int>
#define vl vector<ll>
//x * y * 1.0 can cause overflow
//constant
#define inf (int)(1e9+7)
#define mod (ll)(1e9+7)
#define eps 1e-10
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
//omission
#define eb emplace_back
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define all(v) v.begin(), v.end()
//manip
template<class T> bool chmax(T &a, T b) {if (a < b) {a = b; return 1;} return 0;}
template<class T> bool chmin(T &a, T b) {if (a > b) {a = b; return 1;} return 0;}
#define UNIQUE(v) v.erase(unique(v.begin(), v.end(), v.end())
#define fill(x, y) memset(x, y, sizeof(x))
#define ceil(a, b) a / b + !!(a % b)
template<class T> T power(T a, T b)
{return b ? power(a * a % inf, b / 2) * (b % 2 ? a : 1) % inf : 1;}
#define LB(v, x) (int)(lower_bound(v.begin(), v.end(), x) - v.begin())
#define UB(v, x) (int)(upper_bound(v.begin(), v.end(), x) - v.begin())
//output
#define out(a) cout << a << endl
#define outa(a, n) rep(i, n) cout << a[i] << " "; cout << endl
#define outv(v) rep(i, SZ(v)) cout << v[i] << " "; cout << endl;
#define outp(v) rep(i, SZ(v)) cout << v[i].F << " " << v[i].S << endl
#define outc(s, t) cout << fixed << setprecision(10) << (double)(t - s) / CLOCKS_PER_SEC << endl
//loop
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep3(i, st, n) for (int i = st; i < n; ++i)
#define rrep(i, n) for (int i = n - 1; i >= 0; --i)
//algorithm (have library)
//double pointer, l start, how many adds, can be 0 -> init r = l, sum = 0, while r < n





bool comp(pair<int, pii> a, pair<int, pii> b) {
    //if (a.S.F != b.S.F) return a.S.F > b.S.F;
    //return a.S.S > b.S.S;
    return a.S.F < b.S.F;
}
bool comp2(pair<int, pii> a, pair<int, pii> b) {
    //if (a.S.F != b.S.F) return a.S.F > b.S.F;
    //return a.S.S > b.S.S;
    return a.S.S > b.S.S;
}
int main() {
    //cast caution
    //look constraints always
    cin.tie(0); ios::sync_with_stdio(false);
    
    
    
    
    
    int n, m; cin >> n >> m;
    vector<pair<int, pii> > v;
    int acm3 = 0, acm2 = 0; //ac more than or equal to
    int c = 0;
    int x[n]; fill_n(x, n, 0);
    rep(i, n) {
        int a, b; cin >> x[i] >> a >> b;
        
        x[i]++; //a全員解けてる状態
        if (x[i] - 1 != 3) {
            v.eb(i, pii(a, b));
        } else {
            n--;
            c++;
        }
        
        
        if (x[i] >= 3) {
            acm3++;
        }
        if (x[i] >= 2) {
            acm2++;
        }
    }
    if (c >= m) {
        cout << c << endl;
        return 0;
    }
    
    //cout << endl; cout << acm2 << " " << acm3 << endl;
    sort(all(v), comp);
    
    
    //cout << endl; rep(i, SZ(v)) cout << v[i].F << " " << v[i].S.F << " " << v[i].S.S << endl; cout << endl;
    
    
    
    vector<pair<int, pii> > v2 = v;
    sort(all(v2), comp2);
    
    //cout << endl; rep(i, SZ(v)) cout << v2[i].F << " " << v2[i].S.F << " " << v2[i].S.S << endl; cout << endl;
    
    int ans = inf;
    if (acm2 >= m) ans = acm3;
    rep(sa, inf) {
        //cout << sa << endl;
        while (SZ(v) && v[0].S.F == sa - 1) { //手前の人が解けない
            x[v[0].F]--;
            if (x[v[0].F] == 2) {
                acm3--;
            } else if (x[v[0].F] == 1) {
                acm2--;
            }
            v.erase(v.begin());
        }
        
        //cout << "v " << SZ(v) << endl;
        //cout << nowa << " " << acm2 << " " << acm3 << endl;
        
        if (acm2 >= m) {chmin(ans, acm3); continue;}
        
        //m人以上になるまでbをやさしく
        
        while (acm2 < m && SZ(v2)) {
            x[v2[0].F]++;
            if (x[v2[0].F] == 2) {
                acm2++;
            }
            if (x[v2[0].F] == 3) {
                acm3++;
            }
            v2.erase(v2.begin());
            //cout << v2[0].F << " " << acm2 << " " << acm3 << endl;
        }
        
        if (!SZ(v)) break;
        if (acm2 >= m) {chmin(ans, acm3); continue;}
        
        
        
        
    }
    cout << ans << endl;
}
//cast caution



/*
 目的は2つ
 1. 2完以上をm人以上
 2. 3完以上を最小化
 
 1. の上で2. を目指す
 
 「2完以上m人付近」を全探索すれば答が求まる
 
 毎回操作が一意になるようにしたい
 
 最初
 a 0, b infにする
 
 2完以上m人以上ならa厳しく
 m人未満ならbやさしく
 と、一意に決まる
 
 
 a 0, b inf
 最初m人付近ではないこともある
 m人付近まで
 なんかたどる
 
 あとはm人付近をうろうろ
 
 a inf, b 0でも
 逆の経路みたいになる
 m人付近では同じ
 
 
*/
0