akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std; typedef long double ld; typedef long long ll;
typedef unsigned long long ull;
#define endl "\n"
#define MP make_pair
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORR(x,arr) for(auto& x:arr)
#define PII pair<int, int>
#define FI first 
#define SE second
#define ALL(x) (x).begin(), (x).end()
const int INF=1<<30; const ll LINF=1LL<<60 ; const ll mod=1e9+7 ;
template<class T>inline bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>inline bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//-------------------
string s;
int ans[100000+5];

void solve(int l, int mid, int r){
	//cout << l << ' ' << mid << ' ' <<  r << endl;
	int Rn = mid-l;
	int Ln = r-mid;
	if(Rn%2==0) ans[mid] += Rn/2, ans[mid-1] += Rn/2;
	else ans[mid] +=  Rn/2, ans[mid-1] += Rn/2+1;
	if(Ln%2==0) ans[mid] += Ln/2, ans[mid-1] += Ln/2;
	else ans[mid] +=  Ln/2+1, ans[mid-1] += Ln/2;
	//cout << ans[mid-1] << ' ' << ans[mid] << endl;
}

int main(){
	cin >> s;
	int n = s.size();
	s[n] = 'R';
	int right = 1;
	int left = 0;
	while(right <= n-1){
		int chge = 0;
		while(!(s[right-1] == 'L' && s[right] == 'R')){
			if(s[right-1]=='R' && s[right]=='L') chge = right;
			right++;
		}
		solve(left, chge, right);
		left = right;
		right += 1;
	}
	FOR(i,0,n-1){
		cout << ans[i] << ' ';
	}
	cout << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <algorithm>
#include <iostream>
#include <list>
#include <map> //連想配列
#include <queue>
#include <set>
#include <stack>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <typeinfo>
#include <vector> //動的配列

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

int main() {
  int a, b;
  std::cin >> a >> b;
  std::string s = std::to_string(a) + std::to_string(b);
  double c = std::stoi(s);
  // std::cout << c << std::endl;
  for (int i = 4; i < 320; i++) {
    //std::cout << c / i << std::endl;

    if (i == c / i) {
      std::cout << "Yes" << std::endl;
      return 0;
    }
  }
  std::cout << "No" << std::endl;
  return 0;
}
// return 1するとエラー出るから気をつけよう


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
	int w,h,n;
	cin >> w >> h >> n;
	int maxx=w,maxy=h,minx=0,miny=0;
	for(int i=0;i<n;i++){
		int x,y,a;
		cin >> x >> y >> a;
		switch(a){
			case 1:
				if(x>minx) minx=x;
				break;
			case 2:
				if(x<maxx) maxx=x;
				break;
			case 3:
				if(y>miny) miny=y;
				break;
			case 4:
				if(y<maxy) maxy=y;
				break;
		}
	}
	cout << max(maxx-minx,0)*max(maxy-miny,0) << endl;
}


Measured memory_bytes: 256
#include<cstdio>
int main(){
	unsigned long long a,b;
	long long x = 1,n = 0;
	scanf("%llu %llu %lld",&a,&b,&x);
	n = (b / x)- (a / x);
	if(a % x == 0) n += 1;
	printf("%lld",n);
	return 0;
}

Measured memory_bytes: 128
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::io::*;
#[allow(unused_imports)]
use std::iter;
#[allow(unused_imports)]
use std::mem::*;
#[allow(unused_imports)]
use std::str::*;
#[allow(unused_imports)]
use std::usize;

#[allow(unused_macros)]
macro_rules! read_cols {
    ($($t:ty),+) => {{
        let mut line = String::new();
        stdin().read_line(&mut line).unwrap();

        let mut it = line.trim()
            .split_whitespace();

        ($(
            it.next().unwrap().parse::<$t>().ok().unwrap()
        ),+)
    }}
}

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let mut line = String::new();
    stdin().read_line(&mut line).unwrap();
    line.trim().to_string().parse().ok().unwrap()
}

#[allow(dead_code)]
fn read_vec<T: FromStr>() -> Vec<T> {
    let mut line = String::new();
    stdin().read_line(&mut line).unwrap();

    line.trim()
        .split_whitespace()
        .map(|s| s.parse().ok().unwrap())
        .collect()
}

fn combi(n: usize, p: usize) -> Vec<usize> {
    // C(n, r) = C(n - 1, r) + C(n - 1, r - 1)
    (0..n+1).fold(Vec::with_capacity(n + 1), |mut c, i| {
        c.push(1);
        for r in (1..i).rev() {
            c[r] = (c.get(r - 1).unwrap() + c.get(r).unwrap()) % p;
        }
        c[0] = 1;
        c
    })
}

fn main() {
    let p = read::<i64>();
    let a = read_vec::<i64>();

    let pu = p as usize;

    let c = combi(pu - 1, pu);

    let pow = (0..p).map(|x| {
        iter::once(1).chain((1..p).scan(1, |prev, _| {
            *prev = (*prev * x) % p;
            Some(*prev)
        })).collect::<Vec<_>>()
    }).collect::<Vec<_>>();

    // 1 - (x - i)^(p - 1)
    //  = 1 mod p when x = i
    //  = 0 mod p otherwise
    let coeffs = a.into_iter().enumerate().filter(|&(_, aa)| aa > 0).map(|(i, _)| i).fold(vec![0; pu], |mut coeffs, i| {
        let ii = i as i64;
        coeffs[0] = (coeffs.get(0).unwrap() + 1) % p;
        for j in 0usize..pu {
            let jj = j as i64;
            coeffs[j] = (coeffs.get(j).unwrap() + (if (p-jj) % 2 == 0 {1} else {-1}) * *c.get(j).unwrap() as i64 * pow[i][pu - 1 - j] + p) % p;
        }
        coeffs
    });

    println!("{}", coeffs.iter().map(|c| c.to_string()).collect::<Vec<String>>().join(" "));
}

Measured memory_bytes: 115068
#include <algorithm>
#include <climits>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <vector>

#define int long long int
constexpr int INF = std::numeric_limits<int>::max();
constexpr int NINF = std::numeric_limits<int>::min();
using namespace std;

vector<int> primes = {2};

bool is_prime(int x) {
  for (auto p : primes) {
    if (x % p == 0) {
      return false;
    }
  }
  return true;
}

void solve() {
  int N;
  cin >> N;

  int x = 3;
  while (primes.back() < N) {
    if (is_prime(x)) {
      primes.push_back(x);
    }
    x+=2;
  }

  cout << primes.back() << endl;
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  solve();
  return 0;
}


Measured memory_bytes: 512
#include "bits/stdc++.h"

using namespace std;

using ll = long long;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int n; cin >> n;
    vector<int> a(n + 1); 
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<int> b(n + 1, -1);
    for (int i = n; i > n / 2; i--) {
        b[i] = a[i];
    }

    for (int i = n / 2; i >= 1; i--) {
        int par = 0;
        for (int j = 2 * i; j <= n; j += i) {
            par += b[j];
        }
        b[i] = (a[i] + 2 - par % 2) % 2;
    }

    int m = 0;
    for (int i = 1; i <= n; i++) m += b[i];
    cout << m << endl;
    for (int i = 1; i <= n; i++)
        if (b[i] % 2 == 1) cout << i << " ";
    cout << endl;

    return 0;
}


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

int main(void){
  int i;
  char str[10];
  
  fgets(str,sizeof(str),stdin);
  
  for(i=1;i<4;i++){
    if(str[i-1]==str[i]){
      printf("Bad\n");
      return 0;
    }
  }
  printf("Good\n");
  
  return 0;
}

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

int main(){
  long long n;
  cin>>n;
  long long a[n];
  long long sum = 0;
  for(long long i = 0;i<n;i++){
    cin >> a[i];
    sum+=a[i];
  }
  long long ave = sum/n;
  long long ans = 115141919;
  for(long long i = ave-1; i <= ave+1;i++){
    long long t=0;
    for(long long j = 0;j < n;j++){
      t += (a[j]-i)*(a[j]-i);
    }
    ans = min(ans,t);
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int const inf = 1<<29;
int main(){
    int n,m;
    cin>>n>>m;
    static int dp[51000];
    dp[0]=0;
    for(int i=0;i<n;i++)dp[i+1]=inf;
    for(int i=0;i<m;i++){
        int d;cin>>d;
        for(int j=d;j<=n;j++){
            dp[j]=min(dp[j],dp[j-d]+1);
        }
    }
    cout<<dp[n]<<endl;
}

Measured memory_bytes: 1356
#include <bits/stdc++.h>
using namespace std;
#define loop(i,a,n) for(int i=a;i<n;i++)
int main()
{     
   int n , t , min=1001 ;
   cin>>n>>t;
   pair <int ,int > p[n];
   loop(i,0,n)
       cin>>p[i].second>>p[i].first;
   sort(p,p+n);
   loop(i,0,n)
   {
       if(p[i].first<=t)
       {
           if(p[i].second<min)
              min=p[i].second;
       }
         
   }
   if (min==1001)
       cout<<"TLE"<<endl;
   else       
       cout<<min<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>

using namespace std;

#define N 200002
#define BASE 100001
#define ll long long
#define MAX(X,Y) ((X) <(Y) ? (Y) : (X))
#define ABS(X) ( (X)<0 ? -(X) : (X) )
int convert[BASE];

int pen[N];
void update(int ind,int val) {
  while(ind<N) {
    pen[ind] += val;
    ind += ind&(-ind);
  }
}
int query(int ind) {
  int ret = 0;
  while(ind>0) {
    ret += pen[ind];
    ind = ind&(ind-1);
  }
  return ret;
}
bool canDoit(int *in,int base,int n) {
  long long num = ( (( (ll)n*(n+1))/2) + 1)/2;
  for(int i=1;i<=n;++i) {
    if(in[i]<base) {
      convert[i] = -1;
    } else {
      convert[i] = 1;
    }
    convert[i] += convert[i-1];
  }
  for(int i=1;i<N;++i) {
    pen[i] = 0;
  }
  for(int i=n;i;--i) {
    update(convert[i] + BASE,1);
    int x = convert[i-1] + BASE - 1;
    num -= n-i +1 - query(x);
  }
  if(num<=0) {
    return true;
  }
  return false;
}
void solve() {
  int n;
  int in[BASE];
  scanf("%d",&n);
  for(int i=1;i<=n;++i) {
    scanf("%d ",&in[i]);
  }
  int l = 0, r= 1e9,mid;
  while(l<r) {
    mid = (l+r+1)/2;
    if(canDoit(in,mid,n)) {
      l = mid;
    } else {
      r = mid-1;
    }
  }
  printf("%d\n",l);
}
int main() {
  //freopen("input.txt","r",stdin);
  solve();
  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) for(auto x : v){cout << x << " ";} cout << endl
#define printVS(vs) for(auto x : vs){cout << x << endl;}
#define printVV(vv) for(auto v : vv){for(auto&& x : v){cout << x << " ";}cout << endl;}
#define printP(p) cout << p.first << " " << p.second << endl
#define printVP(vp) for(auto p : vp) printP(p);

typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<Pii> vp;
typedef vector<vector<int>> Graph;
const int inf = 1e9;
const int mod = 1e9 + 7;

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int n, m;
    cin >> n >> m;
    vi le(n + 2), rw(n + 2);
    rep(i, m) {
        string s;
        cin >> s;
        rep(j, n) {
            (s[j] == 'W' ? rw[j + 1] : le[j + 1])++;
        }
    }

    rep(i, n) {
        le[i + 1] += le[i];
    }
    rrep(i, n) {
        rw[i] += rw[i + 1];
    }

    int ans = -1;
    int mi = inf;
    rep(i, n + 1) {
        if (mi > le[i] + rw[i + 1]) {
            mi = le[i] + rw[i + 1];
            ans = i;
        }
    }
    cout << ans << " " << ans + 1 << endl;
}

Measured memory_bytes: 3312
#include <stdio.h>

int main(void) {

	int n, m;
	int a[100][100];
	int b[100];

	scanf("%d %d", &n, &m);

	for (int n_i = 0; n_i < n; n_i++) {
		for (int m_i = 0; m_i < m; m_i++) {
			scanf("%d", &a[n_i][m_i]);
		}
	}

	for (int b_i = 0; b_i < m; b_i++) {
		scanf("%d", &b[b_i]);
	}

	for (int n_i = 0; n_i < n; n_i++) {
		int ans = 0;
		for (int m_i = 0; m_i < m; m_i++) {
			ans += a[n_i][m_i] * b[m_i];
			if (m_i == m - 1) {
				printf("%d\n", ans);
			}
		}
	}

	return 0;
}




Measured memory_bytes: 2084
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i < (int)(n); i++)
using ull = unsigned long long;
using ll = long long;

struct pos {
    int x, y;
};

int main() {

    while (true) {
        int W, H;
        cin >> W >> H;
        if (W*H == 0) break;

        bool C[W][H] = {};
        rep(y, H) rep(x, W) cin >> C[x][y];

        int cnt = 0;
        stack<pos> s;
        rep(y, H) rep(x, W) {
            if (C[x][y]) {
                cnt++;
                s.push({x, y});
            }
            while (!s.empty()) {
                pos p = s.top();
                s.pop();
                C[p.x][p.y] = false;
                for (int dx=-1; dx<=1; dx++) {
                    for (int dy=-1; dy<=1; dy++) {
                        int nx = p.x+dx, ny = p.y+dy;
                        if ((nx<0) || (nx>=W) || (ny<0) || (ny>=H)) continue;
                        if (C[nx][ny]) {
                            s.push({nx, ny});
                            // cout << p.x << p.y << " " << nx << ny << endl;
                        }
                    }
                }
            }
        }
        cout << cnt << endl;
    }

    return 0;
}




Measured memory_bytes: 3212
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) {
		FastReader scan = new FastReader();
		char c = scan.next().charAt(0);
		if(c == 'A') System.out.println('T');
		else if(c == 'T') System.out.println('A');
		else if(c == 'C') System.out.println('G');
		else System.out.println('C');
	}
	
	
	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    }

}


Measured memory_bytes: 21076
#include <cstdio>
#include <algorithm>

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

using namespace std;

typedef unsigned long long ull;

const ull B = 100000007;

int n, m;
char a[50][51];
char b[50][51];
ull f[50][50];

int main(){
  scanf("%d%d", &n, &m);
  rep(i, n){
    scanf("%s", a[i]);
  }
  rep(i, m){
    scanf("%s", b[i]);
  }

  rep(i, m){
    ull e = 0;
    rep(j, m){
      e = e * B + b[i][j];
    }
    f[i][0] = e;
  }
  ull p = 0;
  rep(i, m){
    p = p * B + f[i][0];
  }

  ull t = 1;
  rep(i, m){
    t *= B;
  }
  rep(i, n){
    ull e = 0;
    rep(j, m){
      e = e * B + a[i][j];
    }
    rep(j, n - m + 1){
      f[i][j] = e;
      e = e * B - t * a[i][j] + a[i][j + m];
    }
  }
  rep(j, n - m + 1){
    ull e = 0;
    rep(i, m){
      e = e * B + f[i][j];
    }
    rep(i, n - m + 1){
      if(e == p){
        puts("Yes");
        return 0;
      }
      e = e * B - t * f[i][j] + f[i + m][j];
    }
  }
  puts("No");
  return 0;
}

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

int main(){
    int N,a[100000],sum;
    cin >> N;
    for (int i=0; i<N; ++i) {
        cin >> a[i];
        sum += a[i] % 2;
    }
    if (sum%2==0) cout << "YES" << endl;
    else cout << "NO" <<endl;
}


Measured memory_bytes: 640
#include <iostream>
using namespace std;
int main(void){
    int n,c;
    cin >> n >> c;
    
    int cake=0;
    int p;
    for(int i=0;i<c;i++){
        cin >> p;
        cake += p;
    }
    if(cake%(n+1)==0) cout << cake/(n+1) << endl;
    if(cake%(n+1)!=0) cout << cake/(n+1)+1 << endl;
    return 0;
}



Measured memory_bytes: 3100
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int w = sc.nextInt();
        int[][] field = new int[h + 1][w + 1];
        for (int i = 1; i <= h; i++) {
            for (int j = 1; j <= w; j++) {
                field[i][j] = sc.nextInt();
            }
        }
        for (int i = 1; i <= h; i++) {
            for (int j = 1; j <= w; j++) {
                field[i][j] = Math.abs(field[i][j] - sc.nextInt());
            }
        }
        boolean[][][] dp = new boolean[h + 1][w + 1][(h + w) * 80 + 1];
        dp[1][0][0] = true;
        dp[0][1][0] = true;
       for (int i = 1; i <= h; i++) {
            for (int j = 1; j <= w; j++) {
                for (int k = 0; k <= (i + j - 2) * 80; k++) {
                    if (dp[i - 1][j][k]) {
                        dp[i][j][k + field[i][j]] = true;
                        dp[i][j][Math.abs(k - field[i][j])] = true;
                   }
                    if (dp[i][j - 1][k]) {
                        dp[i][j][k + field[i][j]] = true;
                        dp[i][j][Math.abs(k - field[i][j])] = true;
                    }
                }
            }
        }
        for (int i = 0; i < dp[h][w].length; i++) {
            if (dp[h][w][i]) {
                System.out.println(i);
                return;
            }
        }
    }
}


Measured memory_bytes: 159524
from collections import deque
def bfs(v):
    todo = deque()
    todo.append(v)
    seen[v] = 0
    while len(todo) > 0:
        v = todo.popleft()
        d = seen[v]
        for w in graph[v]:
            if seen[w] != -1:
                continue
            seen[w] = d + 1
            todo.append(w)


N, X, Y = map(int, input().split())
graph = [[] for _ in range(N)]
for i in range(N-1):
    graph[i].append(i+1)
    graph[i+1].append(i)
graph[X-1].append(Y-1)
graph[Y-1].append(X-1)

cnt = [0 for _ in range(N)]
for i in range(N-1):
    seen = [-1 for _ in range(N)]
    bfs(i)
    for j in range(i+1, N):
        cnt[seen[j]] += 1

for i in range(1, N):
    print(cnt[i])

Measured memory_bytes: 49884
import math
N = int(input())

sqrt_N = math.floor(math.sqrt(N - 1))
conbination = 0
conbination_AeqB = 0
for A in range(1, sqrt_N + 1):

    # B = Aからfloor(N-1 / A)まで
    conbination_AeqB += 1
    conbination += math.floor((N - 1) / A) - A
    # N = 5
    # (1, 1, 4), (1, 2, 3), (1, 3, 2), (1, 4, 1)
    # (2, 1, 3), (2, 2, 1)
    # (3, 1, 2)
    # (4, 1, 1)
    # N = 4
    # (1, 1, 3), (1, 2, 2), (1, 3, 1)
    # (2, 1, 2)
    # (3, 1, 1)
print(conbination_AeqB + conbination * 2)

Measured memory_bytes: 9172
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String line = sc.nextLine();
		int ca=0;
		int cb=0;
		int cc=0;
		String str[] = new String[3];
		for(int i=0;i<3;i++) {
		str[i] = String.valueOf(line.charAt(i));
		}
		for(int i=0;i<3;i++) {
			if(str[i].equals("a")) {
				ca++;
			}else if(str[i].equals("b")) {
				cb++;
			}else {
				cc++;
			}
		}
			if(ca==1&&cb==1&&cc==1) {
				System.out.printf("Yes");
			}else {
				System.out.printf("No");
			}
	}
}

Measured memory_bytes: 24148
#include <string>
#include <map>
#include <vector>
#include <iostream>
using namespace std;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int l = s.size();
    while (true) {
        if (s.substr(0, 7) == "keyence") {
            cout << "YES";
            break;
        } else if (s.substr(l - 7, 7) == "keyence") {
            cout << "YES";
            break;
        }

        bool flag = true;
        for (int i = 1; i < 7; i++) {
            if (s.substr(0, i) + s.substr(l + i - 7, 7 - i) == "keyence") {
                cout << "YES";
                flag = false;
                break;
            }
        }

        if (flag) {
            cout << "NO";
        }
        break;
    }   
}


Measured memory_bytes: 256
#include <cstdio>
#include <stack>
#define f first
#define s second

using namespace std;

typedef long long llint;
const int MAXN = 200005;

int n, A[MAXN];
llint sol;
stack < pair<int,int> > s;

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
		scanf("%d", A+i);

	for (int i = 0; i < n; ++i) {
		while (!s.empty() && s.top().f > A[i]) {
			auto x = s.top(); s.pop();
			int pre = s.empty() ? -1 : s.top().s;
			sol += (llint)x.f * ((llint)x.s-pre) * (i-x.s);
		}
		s.emplace(A[i], i);
	}

	while (!s.empty()) {
		auto x = s.top(); s.pop();
		int pre = s.empty() ? -1 : s.top().s;
		sol += (llint)x.f * ((llint)x.s-pre) * (n-x.s);
	}

	printf("%lld\n", sol);
	return 0;
}


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


int main(){
  int n,m,k;
  cin >> n >> m >>k;
  vector<ll> a(n+1),b(m+1);
  a[0]=0;
  b[0]=0;
  for(int i=0;i<n;i++){
     cin >> a[i+1];
     a[i+1] += a[i];
  }
  for(int i=0;i<m;i++){
      cin >> b[i+1];
      b[i+1] += b[i];
  }
  int t;
  vector<int> c(0);
  
  for(int i=0;i<=n;i++){
    if(a[i]>k) break;
    int x=upper_bound(b.begin(),b.end(),k-a[i])-b.begin();
    c.push_back(x-1+i);
    
  }
  sort(c.begin(),c.end());
  reverse(c.begin(),c.end());
  cout << c[0] << endl;
}

Measured memory_bytes: 7444
N,W  = map(int,input().split())
w = []
v = []
for i in range(N):
    a,b = map(int,input().split())
    w.append(a)
    v.append(b)
BIG = 10**15+1
LEN = 10**3
LEN = LEN*N
dp = [[BIG for i in range(LEN+1)]for j in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0

for i in range(N):
    for j in range(LEN):
        dp[i+1][j] = min(dp[i+1][j],dp[i][j])
        if j+v[i] <= LEN:
            dp[i+1][j+v[i]] = min(dp[i+1][j+v[i]],dp[i][j]+w[i])

ans = 0
for j in range(LEN+1):
    if dp[N][j] <= W and j >= ans:
        ans = j

        
print(ans)
# print(dp)

Measured memory_bytes: 173292
#include <stdio.h>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <iostream>
#include <math.h>
#include <bitset>
#include <iomanip>
#include <queue>
#include <cstring>
using namespace std;

int main() {
	vector<vector<int>> A(3, vector<int>(3));
	vector<vector<bool>>B(3, vector<bool>(3,0));
	int N;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++)cin >> A[i][j];
	}
	cin >> N;
	for (int k = 0; k < N; k++) {
		int z; cin >> z;
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				if (A[i][j] == z)B[i][j] = 1;
			}
		}
	}
	bool c = 0,d=1,e=1;
	for (int i = 0; i < 3; i++) {
		bool r = 1,l=1;
		for (int j = 0; j < 3; j++) {
			if (B[i][j] == 0)r = 0;
			if (B[j][i] == 0)l = 0;
		}
		if (B[i][i] == 0)d = 0;
		if (B[2 - i][i] == 0)e = 0;
		if (r == 1 || l == 1)c = 1;
	}
	if (c==1||d==1||e==1)cout << "Yes" << endl;
	else cout << "No" << endl;

}





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

#define ll long long
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

using namespace std;
const int N = 2e5 + 5;
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, k;
    cin >> n >> k;
    vector < int > v;
    for(int i = 0 ; i < n ; i++){
        int x;
        cin >> x;
        v.push_back(x);
    }
    sort(v.begin(),v.end());
    ll ans = 0;
    for(int i = 0 ; i < int (v.size()) - k ; i++)
        ans += v[i];
    cout << ans;
    return 0;
}


Measured memory_bytes: 1400
from collections import deque
N = int(input())
edge = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    edge[a].append([b, c])
    edge[b].append([a, c])


def BFS(x):
    visited = [False for _ in range(N+1)]
    next_N = [False for _ in range(N+1)]
    INF = float('inf')
    dest = [INF for _ in range(N+1)]
    d = deque()
    visited[x] = True
    dest[x] = 0
    for B, C in edge[x]:
        d.append([B, C])
        next_N[B] = True
        dest[B] = dest[x] + C
    while d:
        now = d.popleft()
        visited[now[0]] = True
        for B, C in edge[now[0]]:
            if visited[B] == False and next_N[B] == False:
                d.append([B, C])
                next_N[B] = True
                dest[B] = dest[now[0]] + C
    return dest

Q, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(Q)]
DEST = BFS(K)
for X, Y in xy:
    print(DEST[X] + DEST[Y])


Measured memory_bytes: 120864
#include "bits/stdc++.h"
#define MOD 1000000007
#define INF 11234567890
#define in std::cin
#define out std::cout
#define rep(i,N) for(int i=0;i<N;++i)
typedef long long int LL;

std::string s, t;
int dp[4123][4123];
int ans;

int main()
{
	while (true)
	{
		s.clear(); t.clear();
		memset(dp, 0, sizeof(dp));
		ans = 0;

		in >> s >> t;
		if (s.empty()) { break; }

		rep(i, s.length())
		{
			rep(j, t.length())
			{
				if (s[i] == t[j]) { dp[i + 1][j + 1] = dp[i][j] + 1; }
				else { dp[i + 1][j + 1] = 0; }
			}
		}
		rep(i, s.length() + 1)
		{
			rep(j, t.length() + 1)
			{
				ans = std::max(ans, dp[i][j]);
			}
		}

		out << ans << std::endl;
	}
	return 0;
}

Measured memory_bytes: 69436
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long int
#define rep(i, a, b) for (int i = a; i < b; i++)
#define revrep(i, a, b) for (int i = a; i >= b; i--)
#define pb push_back
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pii>
#define min3(a, b, c) min(a, min(b, c))

int INF = 1e18;
int mod = 1e9 + 7;

void solve()
{
    int x;cin>>x;
    cout<<(x?0:1)<<endl;
}

signed main()
{


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


Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define ll long long
#define rg register
using namespace std;
const int MAXN=53e4+10;
const int Mod=924844033;
struct gao{   int u,v,Next;   }Edge[MAXN<<1];
int n,Es,First[MAXN],Num[MAXN],Tot[MAXN];
int A[MAXN],B[MAXN],Fac[MAXN]={1},Invf[MAXN];
inline int Read()
{   rg int a=0,c=1;   rg char b=getchar();
	while(b!='-'&&(b<'0'||b>'9'))b=getchar();
	if(b=='-')c=-1,b=getchar();
	while(b>='0'&&b<='9')a=a*10+b-48,b=getchar();
	return a*c;
}
inline int Fast(rg int Di,rg int Mi)
{   rg int Back=1;
	for(;Mi>=1;Mi>>=1,Di=1ll*Di*Di%Mod)
		if(Mi&1) Back=1ll*Back*Di%Mod;
	return Back;
}
struct jin
{   int Rader[MAXN],Len,Ms,Inv;
	inline void NTT(int *P,rg int opt)
		{   for(rg int i=1;i<Len;i++)
				if(i<Rader[i]) swap(P[i],P[Rader[i]]);
			for(rg int i=1;i<Len;i<<=1)
			{   rg int Euler=Fast(5,(Mod-1)/(i<<1));
				if(opt<0) Euler=Fast(Euler,Mod-2);
				for(rg int Pos=i<<1,j=0;j<Len;j+=Pos)
				{   rg int Wi=1;
					for(rg int k=0;k<i;k++,Wi=1ll*Wi*Euler%Mod)
					{   rg int X=P[j+k],Y=1ll*P[i+j+k]*Wi%Mod;
						P[j+k]=(X+Y)%Mod,P[i+j+k]=(1ll*X-Y+Mod)%Mod;
					}
				}
			}
			if(opt>0) return ;   else Inv=Fast(Len,Mod-2);
			for(rg int i=0;i<Len;i++) P[i]=1ll*P[i]*Inv%Mod;
		}
	inline void Prepare(rg int Lx)
		{   Ms=-1;
			for(Len=1;Len<=Lx;Len<<=1) Ms++;
			for(rg int i=0;i<Len;i++) Rader[i]=(Rader[i>>1]>>1)|((i&1)<<Ms);
		}
}NTT;
inline int C(rg int A,rg int B){   return 1ll*Fac[A]*Invf[B]%Mod*Invf[A-B]%Mod;   }
inline void Link(rg int u,rg int v)
{   Edge[++Es]=(gao){u,v,First[u]},First[u]=Es;   }
inline void Dfs(rg int Now,rg int Ba)
{   Tot[Now]=1;
	for(rg int i=First[Now];i!=-1;i=Edge[i].Next)
	{	rg int v=Edge[i].v;   if(v==Ba) continue ;
		Dfs(v,Now),Tot[Now]+=Tot[v],Num[Tot[v]]++;
	}
	Num[n-Tot[Now]]++;
}
int main()
{   n=Read();
	memset(First,-1,sizeof(First));
	for(rg int i=1;i<=n;i++) Fac[i]=1ll*Fac[i-1]*i%Mod;
	Invf[n]=Fast(Fac[n],Mod-2);
	for(rg int i=n-1;i>=0;i--) Invf[i]=1ll*Invf[i+1]*(i+1)%Mod;
	for(rg int i=1,u,v;i<n;i++) u=Read(),v=Read(),Link(u,v),Link(v,u);
	Dfs(1,1),NTT.Prepare(n<<1);
	for(rg int i=1;i<=n;i++) A[i]=1ll*Num[i]*Fac[i]%Mod,B[i]=Invf[n-i];
	NTT.NTT(A,1),NTT.NTT(B,1);
	for(rg int i=0;i<NTT.Len;i++) A[i]=1ll*A[i]*B[i]%Mod;
	NTT.NTT(A,-1);
	for(rg int i=1;i<=n;i++) printf("%lld\n",((1ll*n*C(n,i)-1ll*Invf[i]*A[n+i])%Mod+Mod)%Mod);
}


Measured memory_bytes: 27520
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>

//#include <tuple>

//#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define ll long long
#define pb push_back

int main() {
  int h, a;
  cin >> h >> a;
  if (h%a == 0) cout << h/a << endl;
  else cout << h/a+1 <<endl;
  
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(void) {
  string str;
  int a, b, m;
  
  cin >> a >> b >> m;
  
  vector<int> fri(a);
  vector<int> mic(b);
  vector<int> disc(m);
  
  for(int i=0; i<a; i++){
    cin >> fri.at(i);
  }
  
  for(int i=0; i<b; i++){
    cin >> mic.at(i);
  }
  
  for(int i=0; i<m; i++) {
    int x, y, minus;
  	cin >> x >> y >> minus;
    disc.at(i) = fri.at(x-1) + mic.at(y-1) - minus;
  }
  
  int fmin = *std::min_element(fri.begin(), fri.end());
  fmin += *std::min_element(mic.begin(), mic.end());
  int dmin = *std::min_element(disc.begin(), disc.end());
  
  cout << min(fmin,dmin) << endl;
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
#define ll long long                                    // long long省略
#define pb push_back                                    // push_back省略
#define mp make_pair                                    // make_pair省略
#define fi first                                        // first省略
#define se second                                       // second省略
#define itn int                                         // int誤字保険
#define count cout                                      // cout誤字保険
#define vecotr vector                                   // vector誤字保険
#define ednl endl                                       // endl誤字保険
#define opt() cin.tie(0); ios::sync_with_stdio(false)   // 入出力速度改善

#define rep(i,l,r) for(ll i=(l);i<(r);i++)               // 範囲[l, r)で刻み1のfor文(順方向)
#define repp(i,l,r,k) for(ll i=(l);i<(r);i+=(k))         // 範囲[l, r)で刻みkのfor文(順方向)
#define rrep(i,l,r) for(ll i=(r-1);i>=(l);i--)           // 範囲[l, r)で刻み1のfor文(逆方向)
#define rrepp(i,l,r,k) for(ll i=(r-1);i>=(l);i-=(k))     // 範囲[l, r)で刻みkのfor文(逆方向)
#define all(x) (x).begin(), (x).end()                   // vectorのポインタ位置指定用
#define max(p,q)((p)>(q)?(p):(q))                       // max拡張
#define min(p,q)((p)<(q)?(p):(q))                       // min拡張
#define bit(n,m)(((n)>>(m))&1)                          // 変数nのm番目のbitを取り出す

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 dy[]={0, 1, 0, -1};                                 // 4方向近傍
int dx[]={1, 0, -1, 0};                                 // 4方向近傍

#define INF ((1LL<<62)-(1LL<<31))
//#define MOD 998244353
#define MOD 1000000007
#define invp(a,p) pom(a,p-2,p)

////////////////////////////////////////////////////////////////////////////////////////
int main(){
    ll n; cin >> n;
    ll a[n]; rep(i,0,n) cin >> a[i];

    map<ll, ll> d;
    rep(i,0,n) d[a[i]]++;

    ll res = 1;
    rep(i,1,n-1) res = max(res, d[i-1]+d[i]+d[i+1]);
    cout << res << ednl;
}

Measured memory_bytes: 7296
#include <iostream>
#include <string.h>

int main()
{
    char main_string[1000], sub_string[1000];
    std::cin >> main_string;
    std::cin >> sub_string;

    int difference = strlen(main_string) - strlen(sub_string) + 1;
    int max_same_char[difference];
    for (int i = 0; i < difference; i++)
    {
        max_same_char[i] = 0;
        for (int j = i; j < i + strlen(sub_string); j++)
        {
            if (strncmp(&main_string[j], &sub_string[j - i], 1) == 0)
            {
                //if(main_string[j]==sub_string[j]){
                max_same_char[i]++;
            }
        }
        //std::cout << max_same_char[i] << std::endl;
    }
    int max_num = 0;
    for (int i = 0; i < difference; i++)
    {
        if (max_same_char[i] > max_num)
        {
            max_num = max_same_char[i];
        }
    }
    std::cout << strlen(sub_string) - max_num << std::endl;
    return 0;
}

Measured memory_bytes: 3608
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <string>
#include <cmath>
#include <complex>
#include <numeric>
#include <cassert>

#include <vector>
#include <array>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <utility>

#define PI 3.14159265358979323846
#define int64 long long
#define uint64 unsigned long long
#define coutfix(i) cout << fixed << setprecision(i)		//coutの浮動小数出力の桁数設定
using namespace std;

int main()
{
	int64 hh, ww, aa, bb;
	cin >> hh >> ww >> aa >> bb;
	cout << (hh * ww + aa * bb - aa * ww - bb * hh) << endl;
	return 0;
}

Measured memory_bytes: 3620
#include <stdio.h>
#include <string.h>
char buf[1000000];
char temp[1000000];
int main()
{
  int n,i,j,t;
  char c;
  for(;;){
    scanf("%d",&n);
    if(n==0) break;
    scanf("%s",buf);
    while(n-- > 0){
      c = buf[0]; i = 0; j = 1; t = 0;
      while(buf[++i] != '\0'){
	if(c == buf[i]) j++;
	else {
	  t += sprintf(&temp[t],"%d%c",j,c);
	  c = buf[i];
	  j = 1;
	}
      }
      sprintf(&temp[t],"%d%c",j,c);
      strcpy(buf,temp);
    }
    printf("%s\n",buf);
  }
  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
using namespace std;
int main()
{
	int N,M;
	cin >> N >> M;

	double x;

	vector<int> A(N);

	for(int i = 0; N > i; i++){
		cin >> A[i]; 
	}

	for(int i = 0; N > i; i++){
		x = x + A[i];
	}

	x = x / (4*M);


	int num = 0;

	for(int i = 0; N > i; i++){
		if(A[i] >= x){
			num++;
		}
	}

//	cout << num;

	if(num >= M){
		cout << "\nYes";
	}
	else
		cout << "\nNo";

	return 0;
}


Measured memory_bytes: 888
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long LL;
 
template<class T>
    using min_queue = priority_queue<T, vector<T>, greater<T> >;
template<class T>
    using max_queue = priority_queue<T>;

template<class A, class B>
ostream& operator<<(ostream& s, pair<A, B> const& a){
  return s << "(" << get<0>(a) << ", " << get<1>(a) << ")";
}
 
 
template <size_t n, typename... T>
typename std::enable_if<(n >= sizeof...(T))>::type
    print_tuple(std::ostream&, const std::tuple<T...>&) { }
template <size_t n, typename... T>
typename std::enable_if<(n < sizeof...(T))>::type
    print_tuple(std::ostream& os, const std::tuple<T...>& tup) {
    if (n != 0) os << ", ";
    os << std::get<n>(tup);
    print_tuple<n+1>(os, tup);
}
template <typename... T>
std::ostream& operator << (std::ostream& os, const std::tuple<T...>& tup) {
    os << "(";
    print_tuple<0>(os, tup);
    return os << ")";
}
 
template<class T>
ostream& print_collection(ostream& s, T const& a){
  s << '[';
  for(auto it = begin(a); it != end(a); ++it){
    s << *it;
    if(it != prev(end(a))) s << ", ";
  }
  return s << ']';
}
template<class T, class U>
ostream& operator<<(ostream& s, map<T, U> const& a) { return print_collection(s, a); }
template<class T>
ostream& operator<<(ostream& s, set<T> const& a) { return print_collection(s, a); }
template<class T>
ostream& operator<<(ostream& s, vector<T> const& a) { return print_collection(s, a); }
 
const LL INF = 0x3f3f3f3f3f3f3f3fll;
const double PI = acos(-1.0), eps = 1e-7;
const int max3 = 510, max4 = 20100, max5 = 201000, max6 = 2000100, inf = 0x3f3f3f3f;
const int MOD = 1007;


int main() {
    int n;
    cin >> n;
    int now = inf;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        if (tmp == now) {
            ans++;
            tmp = inf;
        }
        now = tmp;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
r, g, b, n = [int(i) for i in sys.stdin.readline().split()]
memo_ls = [[0 for j in range(n+1)] for i in range(4)]
memo_ls[0][0] = 1
for i, color in enumerate(sorted([r, g, b]), 1):
    for j in range(n + 1):
        if j >= color:
            memo_ls[i][j] = memo_ls[i-1][j] + memo_ls[i][j-color]
        else:
            memo_ls[i][j] = memo_ls[i-1][j]
print(memo_ls[-1][-1])

Measured memory_bytes: 3188
from operator import itemgetter
from itertools import accumulate
 
n = int(input())
a = sorted((tuple(map(int, input().split())) for _ in range(n)),
           key=itemgetter(1))
c, d = (map(itemgetter(i), a) for i in (0, 1))
print('YNeos'[any(x > y for x, y in zip(accumulate(c), d))::2])


Measured memory_bytes: 31972
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,k;
  cin>>n>>k;
  int use[10];
  fill_n(use,10,1);
  for(int i=0;i<k;i++){
    int d;
    cin>>d;
    use[d]=0;
  }
  for(int i=n;i<100000;i++){
    int t=i;
    int f=0;
    while(t){
      if(use[t%10]==0)f=1;
      t/=10;
    }
    if(f)continue;
    cout<<i<<endl;
    break;
  }
  return 0;
}


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

using namespace std;

#define io freopen("test.txt", "r", stdin);
#define fast ios_base::sync_with_stdio(0);cin.tie(0);


#define ull unsigned long long int
#define lli long long int
#define li long int
#define ld long double

#define cout(x) cout<<x<<" "
#define coutn(x) cout<<x<<endl
#define newline cout<<endl

#define sz(x) (int)x.size()
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define ar array

#define pii pair<int,int>
#define pll pair<lli,lli>
#define pps pair<pair<int,int>, string>

const int MOD=1000000007;
const lli INF=1e18;
const int MX=100001;
const int N=1000000;


void solve(){

    string s;
    cin>>s;

    if(s[s.size()-1]=='s') s+="es";
    else s+="s";

    cout<<s<<"\n";

}


int main(){
    fast
    // #ifndef godzqa
    //     io
    // #endif

    lli t;
    // cin>>t;
    t=1;
    while(t--){
        solve();
    }
    
    return 0;
}

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

const ll LINF = 1e18;
const int INF = 1e9;
const ll MOD = 1000000007;

template<class T> inline bool chmin(T& a, T b){
    if(a > b){
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b){
    if(a < b){
        a = b;
        return true;
    }
    return false;
}
vector<bool> seen;
void dfs(const Graph &G, int v){
    seen[v] = true; // vを訪問済みにする
    
    for(auto next_v: G[v]){
        if(seen[next_v]) continue; // next_vが探索済みならスルー
        dfs(G, next_v); // 再帰的に探索
    }
}

int main(){

    int n, r;
    cin >> n >> r;
    int nr;
    if(n >= 10){
        nr = r;
    }
    else{
        nr = r+100*(10-n);
    }
    cout << nr << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep2(i, a, n) for(ll i = a; i < (ll)(n); i++)
#define memi cout << endl
#define kono(n) cout << fixed << setprecision(n)
#define all(c) (c).begin(), (c).end()
#define pb push_back
#define hina cout << ‘ ‘
const ll mei = (ll)1e9 + 7;

int main(){
  ll n, k;
  k = 0;
  cin >> n;
  vector<ll> a(n);
  vector<ll> b(n);
  vector<ll> c(n - 1);
  rep(i, n){
    cin >> a[i];
    a[i]--;
  }
  rep(i, n)
    cin >> b[i];
  rep(i, n - 1)
    cin >> c[i];
  rep(i, n){
    if(i != n - 1 && a[i] + 1 == a[i + 1])
      k = k + c[a[i]];
    k = k + b[a[i]];
  }
  cout << k;
  memi;
}

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



int main()
{
    ll a,b,c,k,sum;
    cin>>a>>b>>c>>k;
    if(a>=k){cout<<k;return 0;}
    else
    {
        if(a+b>=k){cout<<a;return 0;}
        else {cout<<2*a+b-k;return 0;}
    }




    return 0;
}


Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define SORT(c) sort((c).begin(), (c).end())
#define pb push_back
using namespace std;

const int INF=10000000;
int V;
struct edge {
    int to,money, time;
};
struct state {
    int from, d;
    bool operator<(const state& a)const{
        return d>a.d;
    }
};
vector<vector<edge> > G;

int d[111];
int ds(int s,int g, int r){
    FOR(i,0,111)d[i]=INF;
    d[s]=0;
    priority_queue<state> q;
    q.push({s,0});
    while(q.size()){
        state sta=q.top();
        q.pop();
        int from=sta.from;
        FOR(i,0,G[from].size()){
            const edge& e=G[from][i];
            int to=e.to;
            int cost=r?e.time:e.money;
            if(d[to]>d[from]+cost){
                d[to]=d[from]+cost;
                q.push({to,d[to]});
            }
        }
    }
    return d[g];
}

int main(){
    int n;
    while(1){
        cin>>n>>V;
        if(!(n||V)) break;
        G=vector<vector<edge> >(n+1);
        FOR(i,0,n){
            int a,b,m,t;cin>>a>>b>>m>>t;
            G[a].pb({b,m,t});
            G[b].pb({a,m,t});
        }
        int k;cin>>k;
        FOR(i,0,k){
            int p,q,r;cin>>p>>q>>r;
            cout<<ds(p,q,r)<<endl;
        }
    }
}

Measured memory_bytes: 1512
N = int(input())
dai = 0
A = list(input().split())
max = int(A[0])
for i in range(1, len(A)):
    if int(A[i]) < int(A[i-1]):
        dai += int(A[i-1]) - int(A[i])
        A[i] = A[i-1]
print(dai)


Measured memory_bytes: 24956
fun main(array: Array<String>) {
    val n = readLine()!!.toInt()
    val one = readLine()!!.split(   " ").map { it.toInt() }
    val two = readLine()!!.split(" ").map { it.toInt() }
    var max = 0
    for(i in 0 until n) {
        for(j in i until n) {
            val temp1 = one.take(i + 1).sum()
            val temp2 = two.takeLast(n - i).sum()
            val temp = temp1 + temp2
            max = if(temp >= max) {
                temp
            }
            else {
                max
            }
        }
    }
    print(max)
}

Measured memory_bytes: 40488
#include <stdio.h>
#include <iostream>
#include <map>

int main(void) {
  int N, M, cnt = 0;
  std::map<std::string, int> m;

  scanf("%d", &N);
  for (int i = 0; i < N; ++i) {
    std::string s;
    std::cin >> s;
    if (m.find(s) != m.end()) {
      m.at(s)++;
    } else {
      m.insert(std::make_pair(s, 1));
    }
  }

  scanf("%d", &M);
  for (int i = 0; i < M; ++i) {
    std::string s;
    std::cin >> s;
    if (m.find(s) != m.end()) {
      m.at(s)--;
    } else {
      m.insert(std::make_pair(s, -1));
    }
  }

  for (std::map<std::string, int>::iterator it = m.begin(); it != m.end(); ++it) {
    cnt = std::max(it->second, cnt);
  }
  printf("%d\n", cnt);

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define N 500000

struct BiT_Node{
  int key;
  struct BiT_Node *p;
  struct BiT_Node *left;
  struct BiT_Node *right;
};

typedef struct BiT_Node *Node;

Node root;

void insert (int v){
  Node y = NULL;
  Node x = root;
  Node z;
  z = malloc(sizeof(struct BiT_Node));
  z->key = v;
  z->left = NULL;
  z->right = NULL;
  y = NULL;
  while(x != NULL){
    y = x;
    if(z->key < x->key) x = x->left;
    else x = x->right;
  }
  
  z->p = y;

  if(y == NULL) root = z;
  else if(z->key < y->key) y->left = z;
  else y->right = z;
}

Node treeSuccessor(Node u){
  if(u->right->left != NULL) {
    while(u->left != NULL) u->right = u->right->left;
    return u;
  }
  Node v = u->p;
  while(v != NULL && u == v->right ){
    u = v;
    v = v->p;
  }
  return v;
}

void in_walk(Node u){
  if(u != NULL){
    in_walk(u->left);
    printf(" %d",u->key);
    in_walk(u->right);
  }
}

void pre_walk(Node u){
  if(u == NULL) return;
  printf(" %d",u->key);
  if(u->left != NULL) pre_walk(u->left);
  if(u->right != NULL) pre_walk(u->right);
}

Node find(int key){
  Node u;
  u = root;
  while(u != NULL && key != u->key){
    if(key < u->key) u = u->left;
    else u = u->right;
  }
  return u;
}

void delete(int key){
  Node u;
  Node y;
  Node x;
  u = find(key);
  if(u->left == NULL || u->right == NULL) y = u;
  else y = treeSuccessor(u);
  if(y->left != NULL){
    x = y->left;
  }
  else x = y->right;

  if(x != NULL) x->p = y->p;
  if(y->p == NULL) root = x;
  else {
    if(y == y->p->left){
      y->p->left = x;
    }
    else y->p->right = x;
  }

  if(y != u) u->key = y->key;

  free(y);
}

int main()
{
  int n,i,tmp;
  char buf[20];
  scanf("%d",&n);
  for(i = 0 ; i < n; i++){
    scanf("%s",buf);
    if(buf[0] == 'i'){
      scanf("%d",&tmp);
      insert(tmp);
    }
    else if(buf[0] == 'f') {
      scanf("%d",&tmp);
      if(find(tmp) != NULL) printf("yes\n");
      else printf("no\n");
    }
    else if(buf[0] == 'd'){
      scanf("%d",&tmp);
      delete(tmp);
    }
    else if(buf[0] == 'p') {
      in_walk(root);
      printf("\n");
      pre_walk(root);
      printf("\n");
    }
  }
  return 0;
}




Measured memory_bytes: 25144
#include<iostream>
#include<map>
#include<string>
#include<vector>

using namespace std;

int N;
int B[40];
long long pb[40];
map<int,map<long long,int> > mem;

int dfs(int x,long long cpb){
  if(x==N)return 0;
  long long fpb=cpb>>x;
  if(mem[x].count(fpb))return mem[x][fpb];
  int r=dfs(x+1,cpb);
  if(!(cpb>>x&1)){
    r=max(r,B[x]+dfs(x+1,cpb|pb[x]));
  }
  return mem[x][fpb]=r;
}

int main(){
  while(cin>>N,N){
    mem.clear();
    map<string,int> m;
    vector<string> d[40];
    for(int i=0;i<N;i++){
      string a;
      int c;
      cin>>a>>B[i]>>c;
      m[a]=i;
      d[i].resize(c);
      for(int j=0;j<c;j++){
	cin>>d[i][j];
      }
    }
    for(int i=0;i<N;i++){
      pb[i]=0;
      for(auto e:d[i]){
	pb[i]|=1LL<<m[e];
      }
    }
    cout<<B[0]+dfs(1,pb[0])<<endl;
  }
}

Measured memory_bytes: 16116
#include <bits/stdc++.h>
#include <cstring>
#include <limits>
using namespace std;
#define ll long long int
#define lli long long int
#define fw(i, s, e) for (ll i = s; i < e; ++i)
#define fe(i, s, e) for (ll i = s; i <= e; ++i)
#define fb(i, e, s) for (ll i = e; i >= s; --i)
#define L(T)  \
    ll T;     \
    cin >> T; \
    while (T--)
#define FASTIO                   \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);            \
    cout.tie(nullptr);
#define mem(a, i) memset(a, i, sizeof(a))
#define ld long double
#define endl "\n"
#define in(P) \
    ll P;     \
    cin >> P;
int main()
{
    FASTIO
    char s[200056];
    char t[200056];
    cin >> s >> t;
    ll h1[30], h2[30];
    mem(h1, 0);
    mem(h2, 0);
    ll l = strlen(s);
    ll cnt = 0;
    fw(i, 0, l)
    {
        if (s[i] != t[i])
        {
            cnt++;
        }
    }
    // ll sm = 0;
    // fw(i, 0, 26)
    // {
    //     sm += (fabs(h1[i] - h2[i]));
    // }
    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 4028
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define all(v) v.begin(), v.end()
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define Rep(n) for (ll _ = 0; _ < (ll)(n); _++)

template<class S>S sum(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
ll min(int a,ll b){return min((ll)a,b);} ll min(ll a,int b){return min(a,(ll)b);}
template <class S> void print(vector<S> &v){for(ll i=0; i<(ll)v.size(); i++){cerr << v[i] << ' ';}cerr << endl;}
template <class S> void print(vector<vector<S>> &v) {for (ll i = 0; i < (ll)v.size(); i++) {for (ll j = 0; j < (ll)v[i].size(); j++) {cerr << v[i][j] << ' ';}cerr << endl;}}


int main(){
	int n,m; cin >> n >> m;
	vector<int> a(n);
	rep(i,n) cin >> a[i];
	sort(all(a));
	priority_queue<pair<int,int>> cb;
	Rep(m){
		int b,c; cin >> b >> c;
		cb.push(make_pair(c,b));
	}
	vector<int> na;
	int count = 0;
	while(!cb.empty()){
		auto [c,b] = cb.top();
		cb.pop();
		if(count + b >= n){
			b = n - count;
			Rep(b){
				na.push_back(c);
			}
			break;
		}
		Rep(b){
			na.push_back(c);
		}
		count += b;
	}
	ll ans = 0;
	rep(i,n){
		if(i >= na.size()) ans += a[i];
		else ans += (ll)max(na[i], a[i]);
	}
	cout << ans << endl;
}

Measured memory_bytes: 5216