Submission #4262900


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
using int64 = int64_t;
#define int int64

// n:遺跡数, m:宝石の種類
// iを探索すると, s[i]点獲得して[l[i], r[i]]の全ての宝石を1つずつ獲得する
// 全種類集めることなくスコアを最大化したい
// 全部いもすでメモってから最も重複の小さい区間を探して, 全体からそこを引けば良い?
// 1つずつ区間を引いて行き, 重複がなくなるものを選定する
// 重複が無くならない場合はどうすればええねん
// のーぷろでした
// 同じ場合はコストが小さい方を選定すればいいですねハイ


// n:1e5, m:1e5
//
// 1 3 30
// 2 3 40
// 3 6 25
// 6 6 10
//  1  2  3  4  5  6
// 30 70 95 25 25 35
// これだったら, [3,6]が条件に合致してコストが最も小さいので, 105-25=80

// 1 3 90
// 5 7 90
//  1  2  3  4  5  6  7
// 90 90 90  0 90 90 90
// 元から0があるので, 90+90=180

// 1 4 70
//  1  2  3  4
// 70 70 70 70
// [1,4]が合致して, 70-70=0

// 1 3 30
// 2 3 40
// 3 6 25
// 6 6 10
// 1 5 40
//  1   2   3  4  5  6
// 70 110 135 65 65 35

signed main(){
  int n, m; 
  cin>>n>>m;
  vector<int> t(101010, 0);
  int ans = 0;
  for(int i=0;i<n;++i){
    int l,r,s;
   	cin>>l>>r>>s;
   	t[l-1]+=s;
    t[r]  -=s;
    ans   +=s;
  }
  
  for(int i=1;i<101010;++i){
    t[i] += t[i-1];
  }
  
  int mn=1e9+1;
  for(int i=0;i<m;++i){
    mn=min(mn,t[i]);
    //cerr<<t[i]<<endl;
  }
  ans -= mn;
  cout << ans << endl;
  
  return 0;
}

Submission Info

Submission Time
Task C - ハイスコア
User task4233
Language C++14 (GCC 5.4.1)
Score 101
Code Size 1603 Byte
Status
Exec Time 81 ms
Memory 1024 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 30 / 30 70 / 70 1 / 1
Status
× 3
× 23
× 43
× 63
Set Name Test Cases
Sample subtask0-sample01.txt, subtask0-sample02.txt, subtask0-sample03.txt
Subtask1 subtask0-sample01.txt, subtask0-sample02.txt, subtask0-sample03.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt
Subtask2 subtask0-sample01.txt, subtask0-sample02.txt, subtask0-sample03.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt
Subtask3 subtask0-sample01.txt, subtask0-sample02.txt, subtask0-sample03.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt, subtask3-01.txt, subtask3-02.txt, subtask3-03.txt, subtask3-04.txt, subtask3-05.txt, subtask3-06.txt, subtask3-07.txt, subtask3-08.txt, subtask3-09.txt, subtask3-10.txt, subtask3-11.txt, subtask3-12.txt, subtask3-13.txt, subtask3-14.txt, subtask3-15.txt, subtask3-16.txt, subtask3-17.txt, subtask3-18.txt, subtask3-19.txt, subtask3-20.txt
Case Name Status Exec Time Memory
subtask0-sample01.txt 2 ms 1024 KB
subtask0-sample02.txt 2 ms 1024 KB
subtask0-sample03.txt 3 ms 1024 KB
subtask1-01.txt 2 ms 1024 KB
subtask1-02.txt 2 ms 1024 KB
subtask1-03.txt 2 ms 1024 KB
subtask1-04.txt 2 ms 1024 KB
subtask1-05.txt 2 ms 1024 KB
subtask1-06.txt 2 ms 1024 KB
subtask1-07.txt 2 ms 1024 KB
subtask1-08.txt 2 ms 1024 KB
subtask1-09.txt 2 ms 1024 KB
subtask1-10.txt 2 ms 1024 KB
subtask1-11.txt 2 ms 1024 KB
subtask1-12.txt 2 ms 1024 KB
subtask1-13.txt 2 ms 1024 KB
subtask1-14.txt 2 ms 1024 KB
subtask1-15.txt 2 ms 1024 KB
subtask1-16.txt 2 ms 1024 KB
subtask1-17.txt 2 ms 1024 KB
subtask1-18.txt 2 ms 1024 KB
subtask1-19.txt 2 ms 1024 KB
subtask1-20.txt 2 ms 1024 KB
subtask2-01.txt 2 ms 1024 KB
subtask2-02.txt 2 ms 1024 KB
subtask2-03.txt 2 ms 1024 KB
subtask2-04.txt 5 ms 1024 KB
subtask2-05.txt 5 ms 1024 KB
subtask2-06.txt 5 ms 1024 KB
subtask2-07.txt 5 ms 1024 KB
subtask2-08.txt 5 ms 1024 KB
subtask2-09.txt 5 ms 1024 KB
subtask2-10.txt 5 ms 1024 KB
subtask2-11.txt 5 ms 1024 KB
subtask2-12.txt 5 ms 1024 KB
subtask2-13.txt 5 ms 1024 KB
subtask2-14.txt 5 ms 1024 KB
subtask2-15.txt 5 ms 1024 KB
subtask2-16.txt 5 ms 1024 KB
subtask2-17.txt 5 ms 1024 KB
subtask2-18.txt 5 ms 1024 KB
subtask2-19.txt 5 ms 1024 KB
subtask2-20.txt 5 ms 1024 KB
subtask3-01.txt 17 ms 1024 KB
subtask3-02.txt 41 ms 1024 KB
subtask3-03.txt 56 ms 1024 KB
subtask3-04.txt 79 ms 1024 KB
subtask3-05.txt 81 ms 1024 KB
subtask3-06.txt 80 ms 1024 KB
subtask3-07.txt 79 ms 1024 KB
subtask3-08.txt 79 ms 1024 KB
subtask3-09.txt 81 ms 1024 KB
subtask3-10.txt 79 ms 1024 KB
subtask3-11.txt 79 ms 1024 KB
subtask3-12.txt 79 ms 1024 KB
subtask3-13.txt 79 ms 1024 KB
subtask3-14.txt 79 ms 1024 KB
subtask3-15.txt 78 ms 1024 KB
subtask3-16.txt 80 ms 1024 KB
subtask3-17.txt 79 ms 1024 KB
subtask3-18.txt 80 ms 1024 KB
subtask3-19.txt 80 ms 1024 KB
subtask3-20.txt 78 ms 1024 KB