akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    string s;
    cin >> s;
    int a=0,b=0,c=0,d=0;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == 'N') a++;
        else if(s[i] == 'S') b++;
        else if(s[i] == 'W') c++;
        else if(s[i] == 'E') d++;
    }
    if((a == 0 && b >= 1) || (b == 0 && a >= 1) || (c == 0 && d >= 1) || (d == 0 && c >= 1)){
        cout << "No" << endl;
    }else{
        cout << "Yes" << endl;
    }
    //cout << a << " " << b <<  " " << c <<  " " << d << endl;
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
//#include <regex>

/* g++ -g -std=c++0x */
/* g++ -g -std=c++11 */

using namespace std;

// freopen("input.txt", "rt", stdin);
// freopen("output.txt", "wt", stdout);

#define ALL(c)          (c).begin(), (c).end()
#define ALLR(c)         (c).rbegin(), (c).rend()
#define FOR(i,a,b)      for (int i=(a); i < (b); ++i)
#define FORR(i,a,b)     for (int i=(a); i > (b); --i)
#define FOR_ALL(i,c)    for (__typeof((c).begin()) i=(c).begin();   \
                             i != (c).end(); ++i)
#define FOR_ALLR(i,c)   for (__typeof((c).rbegin()) i=(c).rbegin(); \
                             i != (c).rend(); ++i)
#define SZ(array)       (sizeof(array)/sizeof(array[0]))
#define lc(x)           (x<<1)     /* 2*x */
#define rc(x)           (x<<1 | 1) /* 2*x+1 */
#define lowbit(x)       (x & (-x)) /* 0b10100 -> 0b100 */

typedef long long       LL;
typedef map<int,int>    MII;
typedef pair<int,int>   PII;
typedef set<int>        SI;
typedef vector<bool>    VB;
typedef vector<double>  VD;
typedef vector<int>     VI;
typedef vector<string>  VS;

/* check if a key is in container C */
template <class C>
inline bool in_(const typename C::key_type& k, const C& A)
{ return A.find(k) != A.end(); }
inline bool in_(const string& s, const string& S)
{ return S.find(s) != string::npos; }

int main()
{
/* #ifndef ONLINE_JUDGE */
/*     freopen("foo", "rt", stdin); */
/* #endif */
    std::ios::sync_with_stdio(false);

    string n;
    cin >> n;
    if (n[0] == n[2])
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

Measured memory_bytes: 256
use std::io;
use std::str;

fn main() {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let split: Vec<&str> = input.as_str().split_whitespace().collect();

    let h: i64 = split[0].parse().unwrap();
    let w: i64 = split[1].parse().unwrap();

    for n in 0..w + 2 {
        print!("#");
    }

    // = /n
    println!("");

    for n in 0..h {
        let mut input = String::new();
        io::stdin().read_line(&mut input).unwrap();
        let pict = input.as_str();
        println!("#{}#", pict.replace("\n", ""));
    }

    for n in 0..w + 2 {
        print!("#");
    }
}

Measured memory_bytes: 4352
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

int main(){
	int c,d,a,b=1;
	cin>>c>>d;
	a=min(c,d);
	a=min(a,300000000);
	for(int i=1;i<=a;i++){
		if(c%i==0 && d%i==0){
			b=i;
		}
	}
	cout<<b<<endl;
	return 0;
}

Measured memory_bytes: 3100
H, W = map(int, input().split())
s = [list(input()) for x in range(H)]
d = [[None for y in range(W)] for x in range(H)]
q = []
white = 0
for x in range(H):
  for y in range(W):
    if s[x][y] == '.':
      white += 1
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
q.append([0, 0, 0])

def Haba(x_now, y_now, d_now, s, d, q):
  for i in range(4):
    if 0 <= x_now + dx[i] and x_now + dx[i] < H and 0 <= y_now + dy[i] and y_now + dy[i] < W:
      if s[x_now + dx[i]][y_now + dy[i]] == '.':
        s[x_now + dx[i]][y_now + dy[i]] = '#'
        d[x_now + dx[i]][y_now + dy[i]] = d_now + 1
        q.append([x_now+dx[i], y_now+dy[i], d_now + 1])

while(len(q) > 0):
  x_now, y_now, d_now = q.pop(0)
  Haba(x_now, y_now, d_now, s, d, q)
if d[H - 1][W - 1] is not None:
  ans = white - d[H - 1][W - 1]  - 1
else:
  ans = -1
print(ans)

Measured memory_bytes: 3188
N,M,C=map(int,input().split())
Bs=[int(x) for x in input().split()]
Ans=0
for i in range(N):
    As=[int(x) for x in input().split()]
    D=0
    for j in range(M):
        Cs=As[j]*Bs[j]
        D=D+Cs
    if D+C>0:
        Ans=Ans+1

print(Ans)

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt(), B = sc.nextInt(), C = sc.nextInt();
		if(C >= A && C <= B) System.out.println("Yes");
		else System.out.println("No");
	}
}


Measured memory_bytes: 21972
#include <bits/stdc++.h>
using namespace std;
using ll = long long;


void solve(long long N, std::vector<long double> x, std::vector<std::string> u){
    double a = 0;
    for (int i = 0; i < N; i++)
    {
        const double BTC = 380000.0;
        if(u[i][0]=='J') a+=x[i];
        else a+=x[i]*BTC;
    }
    cout << a << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long double> x(N);
    std::vector<std::string> u(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%Lf",&x[i]);
        std::cin >> u[i];
    }
    solve(N, std::move(x), std::move(u));
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <numeric>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <math.h>
#include <iomanip>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REP1(i, n) for(int i = 2; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main() {
    ll n, k; cin >> n >> k;
    ll a = pow(k - 1, n - 1);
    cout << k * a << endl;
}

Measured memory_bytes: 3912
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<numeric>
#include<map>
#include<queue>
using namespace std;

int main(){
    int x[4][2],d[2];cin>>x[0][0]>>x[0][1]>>x[1][0]>>x[1][1];
    d[0]=x[1][0]-x[0][0];
    d[1]=x[1][1]-x[0][1];

    for(int i=2;i<=3;i++){
        int k=d[0];
        d[0]=-d[1];
        d[1]=k;
        x[i][0]=x[i-1][0]+d[0];
        x[i][1]=x[i-1][1]+d[1];
    }
    cout<<x[2][0]<<" "<<x[2][1]<<" "<<x[3][0]<<" "<<x[3][1]<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
string dp[10001];
int a[10],f[10]={0,2,5,5,4,5,6,3,7,6};
string getmax(string a,string b)
{
    if(a.size()>b.size()) return a;
    else if(a.size()<b.size()) return b;
    return max(a,b);
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) dp[i]="";
    for(int i=1;i<=m;i++) scanf("%d",&a[i]),dp[f[a[i]]]=getmax(dp[f[a[i]]],to_string(a[i]));
    sort(a+1,a+1+m);
    reverse(a+1,a+1+m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        if(i-f[a[j]]>=1&&dp[i-f[a[j]]]!="")
        dp[i]=getmax(dp[i],dp[i-f[a[j]]]+to_string(a[j]));
    cout<<dp[n]<<endl;
}


Measured memory_bytes: 32896
#include <iostream>
#include <fstream>
#include <vector>
#include <string>

#define REP(i, n) for (int i = 0; i < (n); ++i)
using namespace std;

typedef long long ll;

vector<string> week = {"SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"};

int main()
{

    string s;
    cin >> s;

    int x = 0;
    REP(i, 7)
    {
        if (week[i] == s)
        {
            x = i;
            break;
        }
    }

    cout << 7 - x << endl;

    return 0;
}

Measured memory_bytes: 256
n = int(input())
l = list(map(int,input().split()))
 
l.sort()
 
ans = 0
 
for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            if l[i] + l[j] > l[k] and l[i] != l[j] and l[j] != l[k]:
                ans += 1
 
print(ans)

Measured memory_bytes: 9076
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<map>
#include<bitset>
using namespace std;
typedef long long ll;

#define rep(i, n) for(int i = 0;i < (n);i++)
#define repr(i, n) for(int i = (n);i >= 0;i--)
#define repf(i, m, n) for(int i = (m);i < (n);i++)

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1;} return 0;}
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
//////////////////////////////////////////////////


int main() {
    int a, b, c; cin >> a >> b >> c;
    if ((a==b && a!=c)||(a==c && a!=b)||(b==c&&b!=a)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
import numpy as np

N = int(input())
AB = []
for _ in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))
AB = sorted(AB, key=lambda x: x[1])
A, B = list(zip(*AB))
B = np.array(B)
cumsum_A = np.array(A).cumsum()
# print('cumsum_A', cumsum_A)

ans = 'Yes' if np.count_nonzero(B >= cumsum_A) == N else 'No'
print(ans)


Measured memory_bytes: 54940
//package Contest169;


import java.util.*;
import java.io.*;
import java.math.*;


class Main {
    public static void main(String args[] ) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        //Start here:
        
        Scanner sc=new Scanner(System.in);
        int a=sc.nextInt();
        int b=sc.nextInt();
        
        System.out.println(a*b);
        
        
        
        

    }
}

Measured memory_bytes: 35760
#include <iostream>
using namespace std;

int main() {
	int width,height,x,y,r;
	std::cin >> width;
	std::cin >> height;
	std::cin >> x;
	std::cin >> y;
	std::cin >> r;
	
	if(0 <= x - r  && x + r <= width && 0 <= y - r && y + r <= height) {
		std::cout << "Yes" << std::endl;
	}else {
		std::cout << "No" << std::endl;
	}
	return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <cassert>

#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;
typedef long long int ll;
const ll INF = 1000000000000000000;
const double PI = acos(-1);

int main()
{
    string s;
    cin >> s;

    string ans;
    rep(i, s.size()) {
        ans += 'x';
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3512
use itertools::Itertools;
use proconio::input;
use std::collections::HashSet;

fn main() {
    input! {
        n: usize,
        l: [u64; n],
    }
    let ans = l.into_iter().combinations(3)
        .filter(|v| v.len() == v.iter().collect::<HashSet<&u64>>().len())
        .filter(|v| v.iter().sum::<u64>() > 2 * *v.iter().max().unwrap())
        .count();
    println!("{}", ans);
}


Measured memory_bytes: 2140
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
  int N;
  cin >> N;
  queue<ll> lunlun;
  ll x = 0;
  for (int i = 1; i < 10; i++) lunlun.push(i);
  for (int i = 0; i < N; i++) {
    x = lunlun.front();
    lunlun.pop();
    if (x%10 != 0) lunlun.push(10*x+x%10-1);
    lunlun.push(10*x+x%10);
    if (x%10 != 9) lunlun.push(10*x+x%10+1);
  }
  cout << x << endl;
}

Measured memory_bytes: 5196
#include<bits/stdc++.h>
using namespace std;

int main() {
	int N, M;
	cin >> N >> M;
	int s[M];
	char c[M];
	for (int i = 0; i < M; ++i) cin >> s[i] >> c[i], s[i]--;


	int mx;
	if (N == 1) mx = 9;
	if (N == 2) mx = 99;
	if (N == 3) mx = 999;


	for (int i = 0; i <= mx; i++) {
		string i_s = to_string(i);
		if (i_s.size() != N) continue;
		string ans_koho = i_s;
		bool ok = true;
		for (int j = 0; j < M; j++) {
			if (ans_koho[s[j]] != c[j]) ok = false;
		}
		if (ok) {
			cout << i << endl;
			return 0;
		}
	}

	cout << -1 << endl;
	return 0;
}

Measured memory_bytes: 3668
program ABC110B
    implicit none
    integer(8)::i
    integer(8)::flg=0
    integer(8)::N,M,X,Y,Z
    integer(8),allocatable,dimension(:)::A,B

    read(5,*)N,M,X,Y
    allocate(A(N))
    allocate(B(M))
    read(5,*)(A(i),i=1,N)
    read(5,*)(B(i),i=1,M)

    A=iqsort(A)
    B=iqsort(B)

    do i=X+1,Y
        if(B(1)>=i .and. A(N)<i)then
            flg=1
            exit
        end if
    end do

    if(flg==0)then
        print'(A)',"War"
    else
        print'(A)',"No War"
    end if

contains
    recursive function iqsort(ix) result(ires)
      integer(8), allocatable :: ires(:)
      integer(8), intent(in)  :: ix(:)
      integer :: k
      if (size(ix) <= 1) then 
        ires = ix
      else  
        k = ix(size(ix) / 2)
        ires = [iqsort(pack(ix, ix < k)), pack(ix, ix == k), iqsort(pack(ix, ix > k))] 
      end if
    end function iqsort
end program ABC110B

Measured memory_bytes: 640
s = input()
n = len(s)
if n == 1:
  print(0)
  exit()

cnt_e = 0
cnt_o = 0
for i in range(0,n,2):
  if s[i] == '1':
    cnt_o += 1
for i in range(1,n,2):
  if s[i] == '1':
    cnt_e += 1
print(min((n+1)//2 - cnt_o + cnt_e, n//2 - cnt_e + cnt_o))


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 50;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
/* function */
/* main */
int main(){
    int H, W;
    cin >> H >> W;
    vector<vector<char> > field(H, vector<char>(W));
    vector< vector<vector<int> > > cnt(2, vector<vector<int> >(H, vector<int>(W)));
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) cin >> field[i][j];

    for (int i = 0; i < H; i++) {
        int tmp = 0, r = 0;
        for (int l = 0; l < W; l++) {
            while (r < W && field[i][r] == '.') { r++; }
            int d = r - l;
            while (l < r) {cnt[0][i][l++] = d;}
            r++;
        }
    }
    for (int i = 0; i < W; i++) {
        int tmp = 0, r = 0;
        for (int l = 0; l < H; l++) {
            while (r < H && field[r][i] == '.') { r++; }
            int d = r - l;
            while (l < r) {cnt[1][l++][i] = d;}
            r++;
        }
    }

    int ans = 0;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            ans = max(ans, cnt[0][i][j] + cnt[1][i][j] - 1);
        }
    }
    cout << ans << '\n';
}


Measured memory_bytes: 51328
#import <stdio.h>
int main() {
	int M,D;
	scanf("%d %d",&M,&D);
	int ans=0;
	for(int m=1;m<=M;m++){
		for(int d=1;d<=D;d++){
			int x = d%10;
			int y = d/10;
			if(x>=2 && y>=2 && x*y==m) ans++;
		}
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 7504
#if __has_include("debug.h")
    #include "debug.h"
#else  
#include <bits/stdc++.h>
using namespace std;
#define track  1;
#define d(...) 2;
#endif

#define int long long int

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"      

#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define ff first
#define ss second
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)

#define gcd(a,b)            __gcd((a),(b))
#define lcm(a,b)            ((a*b)/gcd(a,b))

void solve();

int32_t main()
{
    #ifdef DEBUG
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
    #endif 

    fast
    
    int t = 1;
	// cin>>t;
	
	while(t--)
	    solve();
	return 0;  
}

int mod(string num, int a) 
{ 
    // Initialize result 
    int res = 0; 
  
    // One by one process all digits of 'num' 
    for (int i = 0; i < num.length(); i++) 
         res = (res*10 + (int)num[i] - '0') %a; 
  
    return res; 
} 

void solve()
{
	int i,j,cnt=0;
	bool flag=0;
	int n,k;

	cin>>n>>k;

	vector<int>a(n+1);

	for(i=1;i<=n;i++)
	{
		cin>>a[i];
	}

	vector<int>cycle;
	set<int>s;

	cycle.push_back(1);

	i=1;

	s.insert(1);

	int start;

	while(!flag)
	{
		if(s.find(a[i])==s.end())
		{
			cycle.push_back(a[i]);
			s.insert(a[i]);
			i=a[i];
		}
		else
		{
			start=a[i];
			flag=1;
		}
		d(s);
		d(cycle);
	}
	d(start);
	d(cycle);

	flag=0;

	vector<int>v;

	for(i=0;i<cycle.size();i++)
	{
		if(cycle[i]==start&&!flag)
		{
			flag=1;
		}

		if(flag)
		{
			v.push_back(cycle[i]);
		}
	}

	d(v);

	if(k<cycle.size())
	{
		cout<<cycle[k]<<endl;
	}
	else
	{
		  k-=cycle.size();
		
		k = k%((int)v.size());
		d(k);
		cout<<v[k]<<endl;

	}

	

}

Measured memory_bytes: 17744
#include <bits/stdc++.h>
using namespace std;

int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  if (A + B > C + D) {
    cout << "Left" << endl;
  }
  if (A + B == C + D) {
    cout << "Balanced" << endl;
  }
  if (A + B < C + D) {
    cout << "Right" << endl;
  }
  
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, k;
  cin >> n >> k;
  int ans=1;
  for(int i=0; i<n; i++) {
    if(k>ans) ans*=2;
    else ans+=k;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>;
using namespace std;
typedef long long int ll;
const ll mod=(ll)1e9+7;

ll v[60];

int main()
{
    ll n,r,a,b,m;
    char c;
    vector<string>v;
    string s;
cin>>n>>m;
vector<vector<ll>>h(n,vector<ll>(m,0));
h[0][0]=1;
for(ll i=0;i<n;i++)
{
    cin>>s;
    v.push_back(s);
}
for(ll i=1;i<n;i++)
{
h[i][0]=h[i-1][0];
if(v[i][0]!='.')
{
    h[i][0]=0;
}
}
    for(ll j=1;j<m;j++)
{
    h[0][j]=h[0][j-1];
    if(v[0][j]!='.')
{
    h[0][j]=0;
}
}
for(ll i=1;i<n;i++)
{
    for(ll j=1;j<m;j++)
{
h[i][j]=(h[i-1][j]+h[i][j-1])%mod;
if(v[i][j]!='.')
{
    h[i][j]=0;
}
}
}

cout<<h[n-1][m-1];
    return 0;
}


Measured memory_bytes: 9088
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n1,n2) for(int i=n1;i<n2;i++)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long int ll;
typedef pair<ll,ll> Pi;
const int INF=(ll)(1LL<<31)-1;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a, b)*b;}
//int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
int n;
string s[110];
int p[110];

struct tt{
	string s;
	int t;
	int num;
};


tt tp[110];
tt ttp[110];
bool operator<(const tt& left,const tt& right){
	if(left.s!=right.s){
		return left.s<right.s;
	}else{
		return left.t>right.t;
	}
}

int main(){
	cin>>n;
	REP(i,n){
		string ss;
		int st;
		cin>>ss>>st;
		tt temp={ss,st,i+1};
		tp[i]=temp;
		ttp[i]=temp;
	}
	sort(tp,tp+n);
	REP(i,n){
		cout<<tp[i].num<<endl;
	}
	
	return 0;

}

Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>

using namespace std;

int main()
{
    int n,d,a,x,h;
    cin >> n >> d >> a;
    
    pair<long long, long long> arr[n];
    for(int i=0; i<n; i++){
        cin >> x >> h;
        h = (h + a -1) / a;
        arr[i].first  = x;
        arr[i].second = h;
    }
    
    sort(arr, arr+n);
    long long pref[n+1]={0};
    
    int j=0;
    long long ans = 0;
    long long current = 0;
    
    for(int i=0; i<n; i++){
        //decide the place where the influenced does not reach out
        while(j<n && arr[i].first + 2*d >= arr[j].first)
            j ++ ;
        
        /*
        long long necessary = max(0LL, arr[i].second - pref[i]);
        ans += necessary;
        pref[i] += necessary;
        pref[i+1] += pref[i]; //continue the preferences by far
        pref[j] -= necessary; //tujitumaawase     
        */
        
        current -= pref[i]; //reduce unavailable parts that had effectives only in the past, i.e., left. 
        long long necessary = max(0LL, arr[i].second - current); //compare necessity and current gain
        ans += necessary;
        current += necessary;
        pref[j] += necessary;
        
    }
    
    
    
    
    cout << ans << endl;
    return 0;
}
/*
    int m,n,k,cand;
    cin >> m >> n >> k;

    int a[m+1] = {0};
    a[0] = n;

    for(int i=0;i<k;i++){
        cin >> cand;
        for(int j=0; j<m+1; j++){
            if(a[j]>0){
                a[j]--;
                a[cand]++;
            }
        }
    }
    
    int maxi=0;
    for(int i=1;i<m+1;i++){
        if(a[i]>maxi) 
            maxi = a[i];
    }

    for(int i=1;i<m+1;i++){
        if(a[i]==maxi) 
            cout << i << endl;
    }


    for(int i=1;i<m+1;i++){
        cout << a[i] << endl;
    }
*/
 



Measured memory_bytes: 4992
#include <iostream>
#include <climits>
#include <vector>
#include <queue>
#include <functional>

using namespace std;

struct Edge
{
	int to, cost;

	Edge( int t, int c ) : to( t ), cost( c )
	{
		return;
	}
};

int dijkstra1( const vector< vector< Edge > > G, const int s, const int t )
{
	const int V = G.size();

	vector<int> dist( V, INT_MAX );
	dist[s] = 0;

	vector<bool> used( V, false );

	while ( true )
	{
		int v = -1;

		for ( int i = 0; i < V; i++ )
		{
			if ( !used[i] && ( v == -1 || dist[i] < dist[v] ) )
			{
				v = i;
			}
		}

		if ( v == -1 )
		{
			break;
		}

		used[v] = true;

		for ( int i = 0; i < G[v].size(); i++ )
		{
			dist[ G[v][i].to ] = min( dist[ G[v][i].to ], dist[v] + G[v][i].cost );
		}
	}

	return dist[t];
}

int dijkstra2( const vector< vector< Edge > > G, const int s, const int t )
{
	const int V = G.size();

	vector<int> dist( V, INT_MAX );

	priority_queue< pair<int,int>, vector< pair<int,int> >, greater< pair<int,int> > > que;
	que.push( make_pair( 0, s ) );

	while ( !que.empty() )
	{
		int cost = que.top().first;
		int cur = que.top().second;
		que.pop();

		if ( dist[ cur ] <= cost )
		{
			continue;
		}

		dist[ cur ] = cost;

		for ( int i = 0; i < G[ cur ].size(); i++ )
		{
			que.push( make_pair( cost + G[ cur ][i].cost, G[ cur ][i].to ) );
		}
	}

	return dist[t];
}

int main()
{
	int n, m;
	cin >> n >> m;

	vector< vector< Edge > > G( n );

	for ( int i = 0; i < m; i++ )
	{
		int a, b, c, d;
		char dummy;

		cin >> a >> dummy >> b >> dummy >> c >> dummy >> d;

		a--;
		b--;

		G[a].push_back( Edge( b, c ) );
		G[b].push_back( Edge( a, d ) );
	}

	int s, t, money, price;
	char dummy;
	cin >> s >> dummy >> t >> dummy >> money >> dummy >> price;

	s--;
	t--;

	cout << money - price - dijkstra1( G, s, t ) - dijkstra2( G, t, s ) << endl;

	return 0;
}

Measured memory_bytes: 1200
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define pb push_back

using namespace std;

signed main(){
  int n;
  cin >> n;
  int sum = 0;
  vector<int> v;
  int in;
  rep(i, n){
    cin >> in;
    sum += in;
    if(in%10 != 0) v.pb(in);
  }
  
  sort(v.begin(), v.end());
    
  rep(i, v.size()){
    if(sum % 10 != 0) break;
    sum -= v[i];
  }
  
  if(sum % 10 == 0) sum = 0;
  cout << sum << endl;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
import heapq

def pResult(a,b,c):
    print(a[1]+b[1]+c[1])


def solve(X: int, Y: int, Z: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    A.sort(reverse = True)
    B.sort(reverse = True)
    C.sort(reverse = True)
    Q = []
    D = set([])
    I = A[0] + B[0] + C[0]
    heapq.heappush(Q,(-I,I,0,0,0))
    k = 0
    while(True):
        if k == K:
            break
        prev = heapq.heappop(Q)
        ai = prev[2]
        bi = prev[3]
        ci = prev[4]
        if (ai,bi,ci) in D:
            continue
        print(prev[1])
        D.add((ai,bi,ci))
        k+=1
        if ai+1 < len(A):
            i = A[ai + 1] + B[bi] + C[ci]
            heapq.heappush(Q,(-i,i,ai+1,bi,ci))
        if bi+1 < len(B):
            i = A[ai] + B[bi + 1] + C[ci]
            heapq.heappush(Q,(-i,i,ai,bi + 1,ci))
        if ci+1 < len(C):
            i = A[ai] + B[bi] + C[ci + 1]
            heapq.heappush(Q,(-i,i,ai,bi,ci + 1))



# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    Z = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(X) ]  # type: "List[int]"
    B = [ int(next(tokens)) for _ in range(Y) ]  # type: "List[int]"
    C = [ int(next(tokens)) for _ in range(Z) ]  # type: "List[int]"
    solve(X, Y, Z, K, A, B, C)

if __name__ == '__main__':
    main()


Measured memory_bytes: 4596
#include <stdio.h>
#include <assert.h>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <array>
#include <vector>
#include <queue>
#include <set>
#include <cmath>
//#include <unordered_map>
//#include <unordered_set>
//#include <boost/container/static_vector.hpp>
//#include <boost/unordered_set.hpp>
//#include <boost/unordered_map.hpp>
//#include <unistd.h>

const int MAX_N = 550;
const int MAX_M = 200050;
const int MAX_Q = 100050;

//const int MAX_N = 550;
//const int MAX_M = 200;
//const int MAX_Q = 100;

int L[MAX_M], R[MAX_M], p[MAX_Q], q[MAX_Q];
int N, M, Q;

int train_num[MAX_N][MAX_N];
int a[MAX_N][MAX_N];
int ret[MAX_N][MAX_N];

int main(int argc, char **argv) {
    //std::cout << "ret:" << std::endl;
    std::cin >> N >> M >> Q;
    for (int i = 1; i <= M; i++) {
        std::cin >> L[i] >> R[i];
    }
    for (int i = 1; i <= Q; i++) {
        std::cin >> p[i] >> q[i];
    }

    //int train_num[MAX_N][MAX_N] = {};
    //int a[MAX_N][MAX_N] = {};
    //int ret[MAX_N][MAX_N] = {};
    
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            train_num[i][j] = 0;
            a[i][j] = 0;
            ret[i][j] = 0;
        }
    }

    for (int i = 1; i <= M; i++) {
        train_num[L[i]][R[i]]++;
    }

    for (int i = 1; i <= N; i++) {
        for (int j = i; j <= N; j++) {
            a[i][j] = train_num[i][j];
            if (j != i) {
                a[i][j] += a[i][j-1];
            }
        }
    }

    for (int j = N; 1 <= j; j--) {
        for (int i = j; 1 <= i; i--) {
            ret[i][j] = a[i][j];
            if (i != j) {
                ret[i][j] += ret[i+1][j];
            }
        }
    }

    for (int i = 1; i <= Q; i++) {
        std::cout << ret[p[i]][q[i]] << std::endl;
    }
    

    return 0;
}

Measured memory_bytes: 6656
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <bitset>
#include <cstring>
#include <map>
#include <math.h>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> P;
#define rep(i,n) for (int i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = 1<<30;
const ll LINF = 1LL<<58;
const int mod = 1000000007;

int main(){
	int n, x, s = 0, ans = 1;
	cin >> n >> x;
	rep(i,n){
		int l;
		cin >> l;
		s += l;
		if(s <= x)ans++;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <cmath>
using namespace std;

int main()
{
  int w, h, n;
  int mw, mh;
  int cnt = 0;

  cin >> w >> h >> n;

  cin >> w >> h;
  for (int i = 1; i < n; i++) {
    cin >> mw >> mh;

    if ((h < mh && w > mw) || (h > mh && w < mw)) {
      cnt += abs(mh - h) + abs(mw - w);
    }
    else {
      cnt += max(abs(h - mh), abs(w - mw));
    }

    w = mw;
    h = mh;
  }

  cout << cnt << '\n';

  return (0);
}

Measured memory_bytes: 3096
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <utility>
#include <functional>
#include <iomanip>
#include <typeinfo>
#include <iterator>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <tuple>
#include <map>
#include <set>
#include <numeric>
using namespace std;

#define all(container) container.begin(), container.end()
#define sortall(container) (sort(container.begin(), container.end()))
#define yn(cond) ((cond) ? (cout << "Yes" << endl) : (cout << "No" << endl))
#define YN(cond) ((cond) ? (cout << "YES" << endl) : (cout << "NO" << endl))
#define LLONG_MAX numeric_limits<long long>::max()
#define INT_MAX numeric_limits<int>::max()

typedef long long       ll;
typedef vector<int>     vi;
typedef vector<ll>      vll;
typedef vector<double>  vd;
typedef vector<bool>    vb;
typedef vector<string>  vs;
typedef vector<char>    vc;
typedef pair<int, int>  pii;
typedef pair<ll, ll>    pll;
typedef vector<pii>     vpii;
typedef vector<pll>     vpll;
typedef vector<vll>		vvll;
typedef vector<vi>		vvi;
typedef vector<vb>		vvb;
typedef vector<vs>		vvs;
typedef vector<vc>		vvc;

typedef struct edge_ {
	ll to;
	ll cost;
} edge;

typedef struct point_ {
	ll x, y;
	point_(ll x = 0, ll y = 0) : x(x), y(y) {}
} point;

constexpr double	PI = 3.14159265358979323846;
constexpr ll		INF = 1 << 15;
constexpr ll		MOD = (ll)1e9 + 7;
constexpr double	EPS = 1e-7;
constexpr int		dy4[4] = { 0, 1, 0, -1 };
constexpr int		dx4[4] = { 1, 0, -1, 0 };
constexpr int		dy8[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
constexpr int		dx8[8] = { 1, 1, 0, -1, -1, -1, 0, 1 };

template<typename T>
istream& operator >> (istream& is, vector<T>& vec) {
	for (T& x : vec) is >> x;
	return is;
}

template<typename T>
ostream& operator << (ostream& os, const vector<T>& vec) {
	for (const T& x : vec) os << x << " ";
	return os;
}

template<typename S, typename T>
istream& operator >> (istream& is, pair<S, T>& p) {
	is >> p.first >> p.second;
	return is;
}

istream& operator >> (istream& is, point& p) {
	is >> p.x >> p.y;
	return is;
}

template<typename S, typename T>
ostream& operator << (ostream& os, const pair<S, T>& p) {
	os << "{" << p.first << " " << p.second << "}";
	return os;
}

ostream& operator << (ostream& os, const point& p) {
	os << "(" << p.x << " " << p.y << ")";
	return os;
}


template <typename T>
void vecOutPadding(vector<T>& vec, string pad = " ") {
	for (const T& elem : vec)
		cout << elem << pad;
}

template <typename T>
void matOut(vector<vector<T>>& mat) {
	for (const auto& row : mat) {
		for (const T& col : row)
			cout << col << " ";
		cout << endl;
	}
}

/******************************************************************************/
/**********************         Don't make WA !!         **********************/
/******************************************************************************/


int main()
{
	string s, t;
	s = "CODEFESTIVAL2016";
	cin >> t;

	int ans = 0;
	for (int i = 0; i < 16; i++)
		if (s[i] != t[i])ans++;
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
using namespace std;
#define MAX 1000000007
typedef long long ll;

int main(){
  int x=700;
  string s;
  cin>>s;
  for(int i=0;i<3;i++){
    if(s[i]=='o') x+=100;
  }
  cout<<x<<endl;
}


Measured memory_bytes: 256
#include "stdio.h"
#include "stdlib.h"
#include "iostream"
#include "math.h"
#include <string.h>


using namespace std;



int main() {
	int n, d, x,a[200];
	int i, j, k=0;
	cin >> n >> d >> x;
	for (i = 0;i < n;i++) {
		cin >> a[i];
		k += (int)(floor((d - 1) / a[i] + 1));
	}
	
	printf("%d\n", k+x);
	

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

int main()
{
  string s, t;
  cin >> s >> t;

  sort(s.begin(), s.end());
  sort(t.begin(), t.end());
  reverse(t.begin(), t.end());

  if (s < t)
    printf("Yes");
  else
    printf("No");
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

int main(void)
{
  int money, C, change;
  scanf("%d", &money);
  C = 1000 - money % 1000;
  if (C==1000)
  {
    change = 0;
  }else
  {
    change = C;
  }
  
  
  printf("%d\n", change);
  return 0;
}

Measured memory_bytes: 1736
#include <stdio.h>
#define N 100
#define INF 10000000
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n, A[N][N];
void dijkstra();

int main(){
  int i, j, u, t, v, c;

  scanf("%d",&n);
  for(i=0; i<n; i++){
    for(j=0; j<n; j++){
      A[i][j] = INF;
    }
  }

  for(i=0; i<n; i++){
    scanf("%d%d",&u,&t);
    for(j=0; j<t; j++){
      scanf("%d%d",&v,&c);
      A[u][v] = c;
    }
  }
  dijkstra();

  return 0;
}

void dijkstra(){
  int i, u, v, m;
  int c[N], d[N];

  for(i=0; i<n; i++){
    c[i] = WHITE;
    d[i] = INF;
  }
  d[0] = 0;
  c[0] = GRAY;

  while(1){
    m = INF;
    u = -1;
    for(i=0; i<n; i++){
      if(c[i] != BLACK && d[i] < m){
	m = d[i];
	u = i;
      }
    }
    if(m == INF) break; 
    c[u] = BLACK;
    for(v=0; v<n; v++){
      if(c[v] != BLACK && A[u][v] != INF){
	if(d[u] + A[u][v] < d[v]){
	  d[v] = d[u] + A[u][v];
	  c[v] = GRAY;
	}
      }
    }
  }
  for(i=0; i<n; i++){
    if(d[i] == INF) {
      printf("%d -1\n", i);
    } else printf("%d %d\n",i ,d[i]);
  }
}

Measured memory_bytes: 636
#include <bits/stdc++.h>
using namespace std;

int main() {
  int R, G, B, N;
  cin >> R >> G >> B >> N;

  int rmax = N / R;
  int gmax = N / G;
  int ans = 0;

  for (int i=0; i<=rmax; i++) {
    for (int j=0; j<=gmax; j++) {
      int zan = N - (i*R) - (j*G);
      if (zan >= 0 && zan % B == 0) {
        ans++;
      }
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx")
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int (i)=0;i<(n);i++)
#define REP(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define MOD 1000000007
#define fcout cout << fixed << setprecision(15)
#define int long long
#define endl "\n"
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)?"YES":"NO")
typedef long long ll;
typedef pair<int, int> P;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int lcm(int a,int b){return a/gcd(a,b)*b;};
int mod(int a,int b){return (a+b-1)/b;};
template<typename A, size_t N, typename T>
void Fill(A(&array)[N],const T &val){std::fill((T*)array,(T*)(array+N),val);}
template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;};
template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;};



signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	rep(i, n) cin >> a[i], a[i]--;

	int ans = 0;
	while(k) {
		if(k % 2) ans = a[ans];
		vector<int> tmp(n);
		rep(i, n) tmp[i] = a[a[i]];
		a = tmp;
		k /= 2;
	}
	cout << ans + 1 << endl;
	return 0;
}

Measured memory_bytes: 6312
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
#define int long long int
#define read(a) int a; cin >> a;
#define readb(a, b) int a, b; cin >> a >> b;
#define readc(a, b, c) int a, b, c; cin >> a >> b >> c;
#define readarr(a, n) int a[(n) + 1] = {}; FOR(i, 1, (n)) {cin >> a[i];}
#define readmat(a, n, m) int a[n + 1][m + 1] = {}; FOR(i, 1, n) {FOR(j, 1, m) cin >> a[i][j];}
#define print(a) cout << a << endl;
#define printarr(a, n) FOR (i, 1, n) cout << a[i] << " "; cout << endl;
#define printv(v) for (int i: v) cout << i << " "; cout << endl;
#define printmat(a, n, m) FOR (i, 1, n) {FOR (j, 1, m) cout << a[i][j] << " "; cout << endl;} cout << endl;
#define all(v) v.begin(), v.end()
#define sz(v) (int)(v.size())
#define pb push_back
#define fi first
#define se second
#define vi vector <int>
#define pi pair <int, int>
#define vpi vector <pi>
#define vvi vector <vi>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
const ll inf = 1e18;
const ll m = 998244353;
int power(int x,int y, int m) 
{ 
    if (y == 0) 
        return 1;
    int p = power(x, y/2, m) % m; 
    p = (p * p) % m; 
  
    return (y%2 == 0)? p : (x * p) % m; 
} 
int modInverse(int a, int m) 
{     
        return power(a, m-2, m); 
}
int mod(int x)
 {
	if(x<0)return -x;
	else return x;
 } 
signed main()
{
  readb(s,w);
  if(w>=s)cout<<"unsafe"<<endl;
  else
  cout<<"safe"<<endl;  
}

Measured memory_bytes: 3592
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;

#define MOD 1000000007

int main() {
  int n;
  cin >> n;
  vector<ll> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  ll ans = 0;
  for (int i = 0; i < 60; ++i) {
    ll one = 0;
    for (int j = 0; j < n; ++j) {
      if ((a[j] >> 1ll * i) & 1ll) {
        one++;
      }
    }
    ll zero = n - one;
    ll two = (1ll << i) % MOD;
    ll res = (one * zero) % MOD;
    res = (res * two) % MOD;
    ans = (ans + res) % MOD;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e7 + 1;
const long long MOD = 1000000007;
const long double PI = 3.1415926;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
typedef long long int ll;
typedef vector<ll> vi;
typedef vector < pair<ll, ll > > vp;
typedef vector <string> vs;
typedef vector <char> vc;
typedef list <ll> lst;

ll n, m, k, ans = 0, sum = 0, cnt = 0;
string s;
char c;

#define Endl endl

/*--------------------template--------------------*/

int main()
{
	cin >> n;
	cout << "ABC" << n << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
int main()
{
    int n, d[300000], mx = 0, mi;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &d[i]);
        
    }
    for (int i = 0; i < n - 1; ++i)
    {
        if (mx >= i)
        {
            mx = max(mx, i + d[i] / 10);
        }
    }
    if (mx < n - 1)
    {
        printf("no\n");
        return 0;
    }
    mi = n - 1;
    for (int i = n - 1; i > 0; --i)
    {
        if (mi <= i)
        {
            mi = min(mi, i - d[i] / 10);
        }
    }
    if (mi <= 0)
    {
        printf("yes\n");
    }
    else
    {
        printf("no\n");
    }
    return 0;
}



Measured memory_bytes: 4316
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <list>
#include <numeric>
#include <stack>
#include <iomanip>
#include <random>
#include <complex>
#include <functional>
#include <tuple>

#define Rep(i,a,b) for(ll i = a; i < b; ++i)
#define rep(i,b) Rep(i,0,b)
#define allof(a) (a).begin(), (a).end()

#define Yes(q) ((q) ? "Yes" : "No")
#define YES(q) ((q) ? "YES" : "NO")
#define Possible(q) ((q) ? "Possible" : "Impossible")
#define POSSIBLE(q) ((q) ? "POSSIBLE" : "IMPOSSIBLE")

using namespace std;

using ll = long long;

constexpr int inf = 1e9 + 7;
constexpr ll infll = 1ll << 60ll;
constexpr ll mod = 1e9 + 7;
// 0~3までは右左下上 4~7までは斜め
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

namespace {
    template<typename T> void chmax(T& a, T b) { a = std::max(a, b); }
    template<typename T> void chmin(T& a, T b) { a = std::min(a, b); }

    void Cout(long long x, const char* end = "\n") { std::cout << x << end; }
    template <typename T> void Cout(const T& x, const char* end = "\n") { std::cout << x << end; }
    template <typename T> void Cout(const std::vector<T>& x, const char* sep = " ", const char* end = "\n") { for (std::size_t i = 0, sz = x.size(); i < sz; i++) { std::cout << x[i] << (i == sz - 1 ? end : sep); } }

    // 標準入出力
    struct inp {
        std::size_t sz;
        inp(std::size_t _sz = 1) : sz(_sz) {}
        template <typename T> operator T () const { T a; std::cin >> a; return a; }
        template <typename T> operator std::vector<T>() const { std::vector<T> a(sz); for (std::size_t i = 0; i < sz; i++) std::cin >> a[i]; return a; }
    };

    // 2次元用の標準入出力
    template<typename T>
    struct inpn {
        std::size_t szi, szj;
        inpn(std::size_t _szi, std::size_t _szj) : szi(_szi), szj(_szj) {}
        operator std::vector<std::vector<T>>() const {
            std::vector<std::vector<T>> a(szi, std::vector<T>(szj));
            for (std::size_t i = 0; i < szi; ++i)
                for (std::size_t j = 0; j < szj; ++j) cin >> a[i][j];
            return a;
        }
    };

    inp inp1; // input one
}


int main() {

    ll n, W;
    cin >> n >> W;
    vector<ll> w(n), v(n);
    rep(i, n) cin >> w[i] >> v[i];

    vector<vector<ll>> dp(n + 1, vector<ll>(W + 1, 0LL));

    rep(i, n) {
        rep(j, W + 1) {
            // 入れない
            chmax(dp[i + 1][j], dp[i][j]);
            // 入れる
            if (j + w[i] <= W)
                chmax(dp[i + 1][j + w[i]], dp[i][j] + v[i]);
        }
    }

    ll ans = 0LL;
    rep(j, W + 1) {
        chmax(ans, dp[n][j]);
    }
    Cout(ans);

    return 0;
}

Measured memory_bytes: 80256
#include<cstdio>
#include<algorithm>
using namespace std;
int n, res = 1e9;
int Sum(int a) {
	if (!a)return 0;
	return a % 10 + Sum(a / 10);
}
int main() {
	scanf("%d", &n);
	int i;
	for (i = 1; i < n; i++) {
		res = min(res, Sum(i) + Sum(n - i));
	}
	printf("%d\n", res);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

priority_queue <int> q;
vector <int> vec[1000005];

int main(){
    ios_base::sync_with_stdio(false);
	cout.precision(10);
	cout << fixed;

    int n, m;
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        int a, b;
        cin >> a >> b;
        vec[a].push_back(b);
    }
    int res = 0;
    for(int i=m; i>=1; i--){
        for(auto c : vec[m-i+1]){
            q.push(c);
        }
        if(!q.empty()){
            int x = q.top();
            q.pop();
            res += x;
        }
    }
    cout << res;
    return 0;
}


Measured memory_bytes: 26752
fun main(args: Array<String>)
{
    val n = readInt()
    val a = readLine()!!.split(" ").map(String::toLong)

    var sum = 0L
    for (item in a) {
        sum += item
    }

    // val ans = LongArray(n)
    // for (i in 0 until n) {
    //     var tmp = 0L
    //     for (k in 1 until n step 2) {
    //         tmp += if (i+k < n) a[i+k] else a[i+k-n]
    //     }
    //     ans[i] = sum - 2*tmp
    // }
    val ans = LongArray(n)
    var tmp = 0L
    for (k in 1 until n step 2) {
        tmp += a[k]
    }
    ans[0] = sum - 2*tmp

    for (i in 1 until n) {
        ans[i] = 2*a[i-1] - ans[i-1]
    }

    println(ans.joinToString(" "))
}


// Read an integer
// Usage: val a = readInt()
private fun readInt() = readLine()!!.toInt()

// Read N integers separated by " "
// Usage: val (a, b, c) = readNInts()
private fun readNInts() = readLine()!!.split(" ").map(String::toInt)

// Read a string
// Usage: val a = readString()
private fun readString() = readLine()!!


Measured memory_bytes: 59988
// 2011/05/23 Tazoe

#include <iostream>
#include <iomanip>
using namespace std;

int main()
{
	while(true){
		int h, m, s;
		cin >> h >> m >> s;
		if(h==-1&&m==-1&&s==-1)
			break;

		int rem = 2*60*60-h*60*60-m*60-s;
		int rh  = rem/60/60;
		int rm  = rem/60%60;
		int rs  = rem%60;
		cout << setw(2) << setfill('0') << rh << ':';
		cout << setw(2) << setfill('0') << rm << ':';
		cout << setw(2) << setfill('0') << rs << endl;

		rem = rem*3;
		rh  = rem/60/60;
		rm  = rem/60%60;
		rs  = rem%60;
		cout << setw(2) << setfill('0') << rh << ':';
		cout << setw(2) << setfill('0') << rm << ':';
		cout << setw(2) << setfill('0') << rs << endl;
	}

	return 0;
}

Measured memory_bytes: 0
#include<stdio.h>
double rounding(double x, int n)
{
	double i, DP = 1;
	double X;
	
	for(i = 0; i < (n - 1); ++i)
	{
		DP *= 10;
	}
	X = x * DP;
	if(x > 0)
		X = (int)(X + 0.5);
	else
		X = (int)(X - 0.5);
	
	return (double)(X / DP);
}

double determinant(double a, double b, double c, double d)
{
	return (a * d) - (b * c);
}

int main(void)
{
	double a, b, c, d, e, f;
	double A, D1, D2;
	double x, y, X, Y;
	
	while(scanf("%lf %lf %lf %lf %lf %lf", &a, &b, &c, &d, &e, &f) != EOF)
	{
		A  = determinant(a, b, d, e);
		D1 = determinant(c, b, f, e);
		D2 = determinant(a, c, d, f);
		x = (D1 / A);
		y = (D2 / A);
		
		X = rounding(x, 4);
		Y = rounding(y, 4);
		
		printf("%.3f %.3f\n", X, Y);
	}
	return 0;
}

Measured memory_bytes: 652
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

int main(){
	int x,i;
	i=1;
	while(cin>>x){
		if(x==0) break;
		cout<<"Case "<<i<<": "<<x<<endl;
		i++;
		}
	return 0;
}

Measured memory_bytes: 1160
import { readFileSync } from "fs";

const read = () =>
  readFileSync(0, "utf8")
    .split("\n")
    .map((line) => line.split(" "));

const main = (input: string[][]) => {
  const colors = input[0].map(Number);

  return new Set(colors).size;
};

console.log(main(read()));


Measured memory_bytes: 29648
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a=new long[n];
        long max = Long.MIN_VALUE;
        for(int i=0;i<n;i++){
            a[i]=sc.nextLong();
            max = Math.max(max,a[i]);
        }
        long absDif = Long.MAX_VALUE;
        int pos = n-1;
        if(max%2==0){
            for(int j=0;j<n;j++){
                if(a[j]==max) continue;
                long cur = Math.abs(a[j]-max/2);
                if(cur<=absDif){
                    pos = j;
                    absDif = cur;
                }
            }
        }
        else{
            for(int j=0;j<n;j++){
                long cur = Math.min(Math.abs(a[j]-(max+1)/2),Math.abs(a[j]-(max-1)/2));
                if(cur<=absDif){
                    pos = j;
                    absDif = cur;
                }
            }
        }
        String ans = max+" "+a[pos];
        System.out.println(ans);
    }
}


Measured memory_bytes: 58084
# coding: utf-8
r, g, b, n = map(int,input().split())
ans = 0
for i in range(n//r+1):
    for j in range(n//g+1):
        if (n-(r*i + g*j))%b == 0 and (n-(r*i + g*j))//b >= 0:
            ans += 1
print(ans)

Measured memory_bytes: 67228
N, M = map(int, input().split())

ABC = []
for _ in range(M):
    a, b, c = map(int, input().split())
    ABC.append((a, b, c))

edges = ABC[:]
NUM_V = N+1 # 番号0のエッジを簡単のため追加

# 最短経路に置き換えるためコストに-1をかける
edges = [(a,b,-1*c) for a,b,c in edges]


# ベルマンフォード
import sys
INT_MAX = sys.maxsize # 9223372036854775807

def bellman_ford(edges,num_v,source):

    dist=[INT_MAX] * num_v
    dist[source]=0

    #辺の緩和
    has_negative = False
    for i in range(num_v):
        for edge in edges:
            if edge[0] != INT_MAX and dist[edge[1]] > dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]
                if i==num_v-1:
                    has_negative = True
    
    if has_negative == False:
        return dist
    
    negative = [False] * num_v
    for i in range(num_v):
        for from_edge, to_edge, cost in edges:
            if dist[from_edge] == INT_MAX:
                continue
            if dist[to_edge] > dist[from_edge] + cost:
                dist[to_edge] = dist[from_edge] + cost
                negative[to_edge] = True
            
            if negative[from_edge] == INT_MAX:
                negative[to_edge] = True
                
    for i, is_negative in enumerate(negative):
        if is_negative:
            dist[i] = -1 * INT_MAX
        
    return dist

longest = bellman_ford(edges, NUM_V, 1)
ans_value = -1 * longest[NUM_V - 1]
if ans_value == INT_MAX:
    print('inf')
else:
    print(ans_value)

Measured memory_bytes: 3572