akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    string a;
    int ans;
    while(1){
        ans = 0;
        cin >> a;
        if(a == "0") break;
        for(int i = 0; i < a.size(); i++){
        	ans += a[i] - '0';
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 3164
def solve():
    N, x = map(int,input().split())
    a = list(map(int,input().split()))

    ans = 0
    for i in range(1,N):
        sm = a[i-1] + a[i]
        if sm - a[i] <= x:
            a[i] -= max(0,sm - x)
            ans += max(0,sm - x)
        else:
            ans += a[i]
            ans += max(0,sm - a[i] - x)
            a[i] = 0

    print(ans)
if __name__ == '__main__':
    solve()


Measured memory_bytes: 85604
#include<bits/stdc++.h>
using namespace std;
struct Str{
	int p,y,ind1,ind2;
};
const int N=1e5+5;
Str D[N];
bool cmp(const Str& P1,const Str& P2){
	if(P1.p==P2.p){
		return P1.y<P2.y;
	}
	return P1.p<P2.p;
}
bool cmp2(const Str& P1,const Str& P2){
	return P1.ind1<P2.ind1;
}
int main()
{
	int n,m,p,y;
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		scanf("%d%d",&p,&y);
		D[i].p=p;D[i].y=y;D[i].ind1=i;
	}
	sort(D,D+m,cmp);
	D[0].ind2=1;
	for(int i=1,top=1;i<m;i++){
		if(D[i].p!=D[i-1].p){
			D[i].ind2=top=1;
		}else{
			D[i].ind2=++top;
		}
	}
	sort(D,D+m,cmp2);
	for(int i=0;i<m;i++){
		printf("%06d%06d\n",D[i].p,D[i].ind2);
	}
	return 0;
} 

Measured memory_bytes: 3072
//***Little by little one travels far***
 
#include<bits/stdc++.h>
using namespace std;
 
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define ll int
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i,n) for(i=0;i<n;i++)
#define forn(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define for1(i, n) for (ll i = 1; i <= (ll)(n); ++i)
#define ford(i, n) for (ll i = (ll)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (ll i = (ll)(a); i <= (ll)(b); ++i)
#define fora(it,x) for(auto it:x)
#define PI 3.14159265
#define sync ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl "\n"
 
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef long double ld;
 
template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

int main()
{
    ll x,a;
    cin>>x>>a;

    if(x<a) cout<<"0";
    else cout<<"10";
}

Measured memory_bytes: 256
import math


def is_prime(n):
    if n == 1:
        return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True


x = int(input())

min_prime = 2

for i in range(x, 10 ** 6):
    if is_prime(i) is True:
        min_prime = i
        break

print(min_prime)


Measured memory_bytes: 3060
def insertionSort(A, n, g, cnt):
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j = j - g
            cnt += 1
        A[j+g] = v
    return cnt

def shellSort(A, n):
    cnt = 0
    mem = len(A)
    G = []
    while mem != 0:
        G.append(mem)
        if mem == 1: mem = 0
        else :
            mem = int(mem / 2)
    m = len(G)
    print(str(m))
    print(' '.join(map(str, G)))
    for i in range(m):
        cnt = insertionSort(A, n, G[i], cnt)
    print(cnt)
    for j in A:
        print(str(j))
        
if __name__ == '__main__':
    N = int(input())
    M = []
    for i in range(N):
        M.append(int(input()))
    shellSort(M,N)


Measured memory_bytes: 45512
#include <iostream>
#include <algorithm>
#include <functional>
#include <utility>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
using namespace std;

#define rep(i,end)   for (int i=0;i<end;i++)
#define all(cont)    begin(cont), end(cont)
typedef long long ll;
typedef vector<ll> vi;
typedef vector<string> vs;
typedef pair<ll, ll> pii;
typedef pair<ll, string> pis;
typedef pair<string, ll> psi;


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

    int a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << max(a*b, c*d) << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
template <class T>
T _gcd(T a, T b) {
    return a % b ? _gcd(b, a % b) : b;
}
template <class _Itr>
typename iterator_traits<_Itr>::value_type
gcd(_Itr first, _Itr last) {
    using value_type = typename iterator_traits<_Itr>::value_type;
    value_type result = *first;
    for (; first != last; ++first) result = _gcd(result, *first);
    return result;
}

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (auto& i : A) cin >> i;
    cout << gcd(A.cbegin(), A.cend()) << endl;
}


Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main(){
    cin.tie(0);
   	ios::sync_with_stdio(false);
    int n;
    cin >> n;
    if(n==100000) cout << "90909" << endl;
    else if(10000<=n && n<= 99999) cout << 909 + (n-10000)+1 << endl;
    else if(1000<= n && n <= 9999) cout << "909" << endl;
    else if(100 <= n && n <= 999) cout << 9+(n-100)+1 << endl;
    else if(10 <= n && n <= 99) cout << "9" << endl;
    else cout << n << endl; 
    return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int main() {
    int d, g;
    cin >> d >> g;
    int p[d], c[d], sum[d];
    rep(i, d) {
        cin >> p[i] >> c[i];
        sum[i] = p[i] * 100 * (i + 1) + c[i];
    }
    int ans = 99999;
    rep(bit, 1 << d) {
        int tAns = 0, tScore = 0;
        bool used[d];
        rep(i, d) {
            if (1 << i & bit) {
                tScore += sum[i];
                tAns += p[i];
                used[i] = true;
            } else
                used[i] = false;
        }
        if (tScore >= g)
            ans = min(ans, tAns);
        else {
            for (int i = d - 1; i >= 0; i--) {
                if (!used[i]) {
                    if (!((double)((g - tScore) / (100 * (i + 1))) > p[i] - 1))
                        ans = min(ans, tAns + (int)ceil((double)(g - tScore) / (double)(100 * (i + 1))));
                    break;
                }
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int a,b;
    cin>>a>>b;
    if(a>b)
    {
        cout<<"a > b"<<endl;
    }
    else if(a==b)
    {
        cout<<"a == b"<<endl;
    }
    else
    {
        cout<<"a < b"<<endl;
    }

    return 0;
}



Measured memory_bytes: 3092
import java.io.*;
import java.util.*;

public class Main {
  private static void execute(ContestReader reader, PrintWriter out) {
    out.println("ABC" + reader.next());
  }
  
  public static void main(String[] args) {
    ContestReader reader = new ContestReader(System.in);
    PrintWriter out = new PrintWriter(System.out);
    execute(reader, out);
    out.flush();
  }
}

class ContestReader {
  private BufferedReader reader;
  private StringTokenizer tokenizer;
  
  ContestReader(InputStream in) {
    reader = new BufferedReader(new InputStreamReader(in));
  }
  
  public String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }
  
  public int nextInt() {
    return Integer.parseInt(next());
  }
  
  public long nextLong() {
    return Long.parseLong(next());
  }
  
  public double nextDouble() {
    return Double.parseDouble(next());
  }
  
  public String[] next(int n) {
    String[] array = new String[n];
    for (int i = 0; i < n; i++) {
      array[i] = next();
    }
    return array;
  }
  
  public int[] nextInt(int n) {
    int[] array = new int[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextInt();
    }
    return array;
  }
  
  public long[] nextLong(int n) {
    long[] array = new long[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextLong();
    }
    return array;
  }
  
  public double[] nextDouble(int n) {
    double[] array = new double[n];
    for (int i = 0; i < n; i++) {
      array[i] = nextDouble();
    }
    return array;
  }
  
  public char[] nextCharArray() {
    return next().toCharArray();
  }
  
  public int[][] nextInt(int n, int m) {
    int[][] matrix = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextInt();
      }
    }
    return matrix;
  }
  
  public long[][] nextLong(int n, int m) {
    long[][] matrix = new long[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextLong();
      }
    }
    return matrix;
  }
  
  public double[][] nextDouble(int n, int m) {
    double[][] matrix = new double[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        matrix[i][j] = nextDouble();
      }
    }
    return matrix;
  }
  
  public char[][] nextCharArray(int n) {
    char[][] matrix = new char[n][];
    for (int i = 0; i < n; i++) {
      matrix[i] = next().toCharArray();
    }
    return matrix;
  }
}


Measured memory_bytes: 22996
#include<bits/stdc++.h>
#include<stdio.h>
#include<queue>

using namespace std;


int main()
{

string st;

cin>>st;

if(st=="Sunny")
    cout<<"Cloudy"<<endl;
else if(st=="Cloudy")
cout<<"Rainy"<<endl;
else if(st=="Rainy")
    cout<<"Sunny"<<endl;


    return 0;
}


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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using ll = long long;
int mod = 1000000000+7;

int main(){

	int a,b,c;
    cin>>a>>b>>c;
  	
  	if(a==b)cout<<c;
  	else if(b==c)cout<<a;
  	else cout<<b;
  	cout<<endl;

	return 0;
}


Measured memory_bytes: 256
use whiteread::parse_line;

fn main() {
    let (mut a, mut b, mut c): (i32, i32, i32) = parse_line().unwrap();
    let mut ans = 0;
    while a % 2 == 0 && b % 2 == 0 && c % 2 == 0 {
        if a % 2 == 1 || b % 2 == 1 || c % 2 == 1 {
            break;
        }
        if a == b && a == c {
            ans = -1;
            break;
        }
        let (at, bt, ct) = (a, b, c);
        a = (bt + ct) / 2;
        b = (at + ct) / 2;
        c = (at + bt) / 2;
        ans += 1;
    }
    println!("{}", ans);
}


Measured memory_bytes: 2132
use std::io;
//use std::collections::HashMap;
//use std::collections::BinaryHeap;
//use std::collections::HashSet;
//use std::mem; // mem::swap(&mut x,&mut y);
//use std::cmp; // cmp::max,cmp::min

// Rust memo: https://hackmd.io/i0lQY1OKTDW1t66TECOmiw?both

#[allow(dead_code)]
fn read_line() -> String{
    let mut s = String::new();
    io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

#[allow(dead_code)]
fn read_charvec() -> Vec<char>{
    read_line().chars().collect()
}

#[allow(dead_code)]
fn read_ints() -> Vec<i64>{
    let s = read_line();
    let split:Vec<&str> = s.split(" ").collect();
    split.iter().map(|&x| x.to_string().parse().unwrap()).collect()
}

#[allow(dead_code)]
fn read_int() -> i64{
    read_ints()[0]
}

#[allow(dead_code)]
fn reverse(s: &String) -> String{
    s.chars().rev().collect::<String>()
}

#[allow(dead_code)]
fn read_lines(n:i64) -> Vec<String>{
    let mut xs = Vec::new();

    for _i in 0..n{
        xs.push(read_line());
    }

    xs
}

#[allow(dead_code)]
fn read_ints2(n:i64) -> Vec<i64>{
    read_lines(n).iter().map(|x| x.parse().unwrap()).collect()
}

#[allow(dead_code)]
fn arange(start:i64,end:i64,step:i64) -> Vec<i64>{
    let mut ret = Vec::new();
    let mut i = start;

    while i < end{
        ret.push(i);
        i += step;
    }

    ret
}

#[allow(dead_code)]
const DXS : [i64; 4] = [0,0,1,-1];
#[allow(dead_code)]
const DYS : [i64; 4]  = [1,-1,0,0];
#[allow(dead_code)]
const INF : i64 = 999999999;

////////////////////////////////////////////////


fn main(){
    let xs = read_ints();
    let _n = xs[0];
    let m = xs[1];
    
    let mut ab : Vec<(i64,i64)> = (0..m)
        .map(|_| read_ints())
        .map(|x| (x[0],x[1]))
        .collect();
    
    ab.sort_by_key(|x| x.1);
    
    let mut disconnect_point = -1;
    let mut n_disconnect = 0;
    
    for (a,b) in ab{
        if disconnect_point <= a{
            n_disconnect += 1;
            disconnect_point = b;
        }
    }
    
    println!("{}",n_disconnect);
}

Measured memory_bytes: 6396
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>

using namespace std;

int main() {
    int N, T, A;
    cin >> N;
    cin >> T >> A;
    int H[N];
    for(int i = 0; i < N; i++) cin >> H[i];
    int cnt = 0;
    double sa = 99999;
    for(int i = 0; i < N; i++) {
        if(sa > abs(A - (T-(H[i]*0.006)))) {
            sa = abs(A - (T-(H[i]*0.006)));
            cnt = i+1;
        }
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
//ABS提出結果からコピー
import java.util.*;
 
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int Y = sc.nextInt();
    int ansA = -1;
    int ansB = -1;
    int ansC = -1;
    BREAK:for (int i=0;i<=N;i++){ 
      for (int j=0;j<=(N-i);j++){
        for (int k=0;k<=(N-i-j);k++){
          int sum = (10000*i)+(5000*j)+(1000*k);
          if ((sum == Y)&&(N == (i+j+k))){
            ansA = i;
            ansB = j;
            ansC = k;
            break BREAK;
          }
        }
      }
    }
    System.out.println(ansA + " " + ansB + " " + ansC);
  }
}

Measured memory_bytes: 21972
#include <bits/stdc++.h>
#include <math.h>
#define REP(i, n) for(int i = 0; i < (n); i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1001001001;
const int mINF = -1001001001;


int main() {
int a;
set<int> st;
REP(i,3) {
  cin >> a;
  st.insert(a);
}
int ans=st.size();
cout << ans << endl;
return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int read(){
	int w=0,f=1;
	char c=' ';
	while(c<'0'||c>'9')c=getchar(),f=c=='-'?-1:f;
	while(c>='0'&&c<='9')w=w*10+c-48,c=getchar();
	return w*f;
}
int n;
int a[N], b[N];
int ca[N], cb[N];
signed main(){
	n = read();
	for(int i = 1; i <= n; i++) a[i] = read(), ca[a[i]]++;
	for(int i = 1; i <= n; i++) b[i] = read(), cb[b[i]]++;
	for(int i = 1; i <= n; i++) if(ca[i] + cb[i] > n) return printf("No\n"), 0;
	reverse(b + 1, b + n + 1);
	vector<int> t;
	int cnt = 0, val = 0, len = 0;
	for(int i = 1; i <= n; i++)
	{
		if(b[i] == a[i])
		{
			cnt++;
			val = b[i];
			t.push_back(i);
		}
	}
	len = cnt;
	vector<int> s;
	for(int i = 1; i <= n; i++)
	{
	 if(a[i] == b[i]) continue;
	 if(cnt == 0) break;
	 if(a[i] != val && b[i] != val)
	 {
	 	s.push_back(i);
	 	cnt--;
	 }		
	}
	for(int i = 0; i < len; i++)
	{
		swap(b[s[i]], b[t[i]]);
	}
	printf("Yes\n");
	for(int i = 1; i <= n; i++) printf("%d ", b[i]);
	printf("\n");
	return 0;
}


Measured memory_bytes: 7356
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 300005
#define ll long long
const int P = 998244353;
char S[N];
int n, ans = 1;
int main()
{
	scanf("%d", &n);
	scanf("%s", S + 1);
	for (int i = 1; i <= n; i++)
		ans = (ll)ans * i % P;
	int r = 0, g = 0, b = 0, rg = 0, rb = 0, gb = 0;
	for (int i = 1; i <= 3 * n; i++)
	{
		if (S[i] == 'R')
		{
			if (gb) {ans = (ll)ans * gb % P, gb--; continue;}
			if (g) {ans = (ll)ans * g % P, g--, rg++; continue;}
			if (b) {ans = (ll)ans * b % P, b--, rb++; continue;}
			r++;
		}
		if (S[i] == 'B')
		{
			if (rg) {ans = (ll)ans * rg % P, rg--; continue;}
			if (g) {ans = (ll)ans * g % P, g--, gb++; continue;}
			if (r) {ans = (ll)ans * r % P, r--, rb++; continue;}
			b++;
		}
		if (S[i] == 'G')
		{
			if (rb) {ans = (ll)ans * rb % P, rb--; continue;}
			if (b) {ans = (ll)ans * b % P, b--, gb++; continue;}
			if (r) {ans = (ll)ans * r % P, r--, rg++; continue;}
			g++;
		}
	}
	printf("%d\n", ans);
}


Measured memory_bytes: 512
#include "bits/stdc++.h"
using namespace std;

//#define int long long
#define DBG 1
#define dump(o) if(DBG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define each(it,c) for(auto it=(c).begin();it!=(c).end();it++)
#define all(c) c.begin(),c.end()
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);

#define MAX 301

int dp[MAX][MAX];
int w[MAX];

int dfs(int l, int r) {
	if (dp[l][r] != -1)return dp[l][r];
	if (r - l >= 3) {
		if (abs(w[r - 1] - w[l]) <= 1 && dfs(l + 1, r - 1) == r - l - 2) 
			return dp[l][r] = r - l;
		else {
			for (int m = l + 1; m < r; m++)
				dp[l][r] = max(
					dp[l][r],
					dfs(l, m) + dfs(m, r)
				);
			return dp[l][r];
		}
	}
	if (r - l == 2)
		if (abs(w[r - 1] - w[l]) <= 1)
			return dp[l][r] = 2;
		else
			return dp[l][r] = 0;
	if (r - l <= 1)return dp[l][r] = 0;
}

signed main() {
	for (int n; cin >> n&&n;) {
		memset(dp, -1, sizeof(dp));
		for (int i = 0; i < n; i++)cin >> w[i];
		cout << dfs(0, n) << endl;
	}
	return 0;
}

Measured memory_bytes: 3432
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		//整数a,bを読み込んで、大小関係を示す
		Scanner sc=new Scanner(System.in);
		int a=sc.nextInt();
		int b=sc.nextInt();
		if(a>b){
			System.out.println("a > b");
		}else if(a<b){
			System.out.println("a < b");
		}else{
			System.out.println("a == b");
		}
	}

}



Measured memory_bytes: 26408
#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define INF 2147483647
#define llINF 9223372036854775807
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long

using namespace std;
int main(){
  int n;
  while(cin>>n,n){
    int toru[n];
    int ohajiki=32;
    int cnt=0;
    for(int i=0;i<n;i++)
      cin>>toru[i];
    while(ohajiki!=0){
      if(cnt%2==0){
	ohajiki-=(ohajiki-1)%5;
	cnt++;
	if(ohajiki<0)
	  ohajiki=0;
	cout<<ohajiki<<endl;
      }else{
	ohajiki-=toru[(cnt/2)%n];
	//cout<<toru[(cnt/2)%n]<<endl;
	cnt++;
	if(ohajiki<0)
	  ohajiki=0;
	cout<<ohajiki<<endl;
      }
    }
  }
  return 0;
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using pi = pair<int, int>;
const ll INF = 1LL << 60;


int main() {
    int n,maxs = 0, cnt=0;
    string s;
    cin >>n>> s;
    for (auto ss : s) {
        if (ss == 'I')cnt++;
        else cnt--;
        maxs = max(cnt, maxs);
    }
    cout << maxs << endl;
    return 0;
}

Measured memory_bytes: 256
n=int(input())
p=list(map(int,input().split()))
id=[0]*(n+1)
for i,p_i in enumerate(p):
    id[p_i]=i

r = list(range(1,n+1))+[n,n]
l = list(range(-1,n-1))+[-1,-1]
ans=0
for p in range(1,n+1):
    x=id[p]
    r1=r[x]
    r2=r[r1]
    l1=l[x]
    l2=l[l1]
    ans+=p*((x-l1)*(r2-r1) + (l1-l2)*(r1-x))
    r[l1]=r1
    l[r1]=l1
print(ans)


Measured memory_bytes: 20180
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9+5;
void solve(){
    int n, k;
    cin >> n >> k;
    int h[n+1];

    for(int i = 1; i <= n; i++){
        cin >> h[i];
    }
    vector<int> dp(n+1, INF);
    dp[1] = 0;
    for(int i = 1; i <= n; i++){
        for(int j = i+1; j <= i+k; j++){
            if(j <= n){
                dp[j] = min(dp[j], dp[i]+abs(h[i] - h[j]));
            }
        }
    }
    cout << dp[n] << endl;
}

int main(){
    solve();
}

Measured memory_bytes: 1024
#include<stdio.h>
#include<stdlib.h>
int c=0;

int* Selection(int *A, int N){
  int i, j, minj, num;
  for(i=0 ; i<N ; i++){
    minj=i;
    for(j=i ; j<N ; j++){
      if(A[j]<A[minj]){
        minj=j;
      }
    }
    num=A[i];
    A[i]=A[minj];
    A[minj]=num;
    if(A[i]!=A[minj])c++;
  }
  return A;
}

int main(void){
  int N,i;
  int *A;
  while(1){
  scanf("%d",&N);
  if(N>=1 && N<=100)break;
}
  A = (int*)malloc(sizeof(int)*N);
  for(i=0 ; i<N ; i++){
    while(1){
    scanf("%d",&A[i]);
    if(0<=A[i] && A[i]<=100)break;
  }
  }
  A=Selection(A,N);
  printf("%d",A[0]);
  for(i=1 ; i<N ; i++){
    printf(" %d",A[i]);
  }
  printf("\n%d\n",c);
  return 0;
}


Measured memory_bytes: 2084
#include <iostream>
#include <vector>

using namespace std;

const int K = 26;

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

    int d;
    cin >> d;
    vector<int> c(K);
    for (int i = 0; i < K; ++i) {
        cin >> c[i];
    }
    vector<vector<int>> s(d, vector<int>(K));
    for (int i = 0; i < d; ++i) {
        for (int j = 0; j < K; ++j) {
            cin >> s[i][j];
        }
    }
    vector<int> ans;
    vector<int> last(26, -1);
    for (int i = 0; i < d; ++i) {
        vector<double> x;
        for (int j = 0; j < K; ++j) {
            x.push_back((double) s[i][j] * s[i][j] * s[i][j] * c[j] * (i - last[j]));
        }

        double sum = 0;
        for (int j = 0; j < K; ++j) {
            sum += x[j];
        }
        for (int j = 0; j < K; ++j) {
            x[j] /= sum;
        }

        double prob = (double) (rand() % RAND_MAX) / (double) RAND_MAX;
        double cur = 0;
        for (int j = 0; j < K; ++j) {
            if (cur + x[j] <= prob) {
                cur += x[j];
                continue;
            }
            ans.push_back(j);
            last[j] = i;
            break;
        }
    }

    for (auto u : ans) {
        cout << u + 1 << "\n";
    }

    return 0;
}

Measured memory_bytes: 3584
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

#define INF 999999999

typedef pair<int,int> P;

int n, m, l;
int t[102][102];
P p[2002];

int V;
vector<int> G[2002];
int match[2002];
bool used[2002];

void floyd(){
  for(int k = 0; k < n; k++){
    for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
        if(i == j) continue;
        t[i][j] = min(t[i][j], t[i][k] + t[k][j]);
      }
    }
  }

  for(int i = 0; i < n; i++){
    t[i][i] = 0;
  }
}

void mkGraph(){
  sort(p, p + l);
  V = l * 2;

  for(int i = 0; i < V; i++){
    G[i].clear();
  }

  for(int i = 0; i < l; i++){
    for(int j = i + 1; j < l; j++){
      if(p[i].first + t[p[i].second][p[j].second] <= p[j].first){
        G[i].push_back(l + j);
        G[l + j].push_back(i);
      }
    }
  }
}

bool dfs(int v){
  used[v] = true;

  for(int i = 0; i < G[v].size(); i++){
    int u = G[v][i];
    int w = match[u];

    if(w < 0 || !used[w] && dfs(w)){
      match[v] = u;
      match[u] = v;
      return true;
    }
  }

  return false;
}

int bipartite_matching(){
  int res = 0;
  memset(match, -1, sizeof(match));

  for(int v = 0; v < V; v++){
    if(match[v] < 0){
      memset(used, 0, sizeof(used));
      if(dfs(v)){
        res++;
      }
    }
  }

  return res;
}

int main(){
  while(cin >> n >> m >> l, n || m || l){
    for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
        t[i][j] = INF;
      }
    }

    for(int i = 0; i < m; i++){
      int a, b, c;
      cin >> a >> b >> c;
      t[a][b] = t[b][a] = c;
    }

    for(int i = 0; i < l; i++){
      cin >> p[i].second >> p[i].first;
    }

    floyd();
    mkGraph();
    cout << l - bipartite_matching() << endl;
  }
}

Measured memory_bytes: 7820
#include <iostream>
#include <queue>
#include <algorithm>
#include <set>
#include <vector>
#include <string>

using namespace std; using ll=long long; const int INF=1e9; using P=pair<ll,ll>;

int main() {
  string s; cin>>s; int n=s.size();
  /*
  ll a[2019]={};
  ll an=0, ga=0;
  for(int i=0;i<n;i++) {
    ll x = s[i]-'0';
    a[(ga+x)%2019]++;
    an+=a[ga];
    ga=ga*10%2019;
    cout<<ga<<endl;
  }
  cout<<an<<endl;*/

  ll a[2][2019]={};
  ll an=0;
  for(int i=0;i<n;i++) {
    int nw=i%2, nx=(i+1)%2;
    fill(a[nx], a[nx]+2019, 0LL);
    a[nx][s[i]-'0']++;
    for(int j=0;j<2019;j++) {
      if (a[nw][j]) a[nx][(j*10+s[i]-'0')%2019]+=a[nw][j];
    }
    an+=a[nx][0];
  }
  cout<<an<<endl;
}

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

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
#define chmax(x, v) do { x = max(x, v); } while (0)
#define chmin(x, v) do { x = min(x, v); } while (0)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

ll N;
vector<ll> edges[202020];
vector<ll> colors(202020, -1);
queue<ll> mod[3];
vector<ll> vertices[2];
vector<ll> ans(202020,-1);

void dfs(ll i, ll col) {
  if (colors[i] != -1)
    return;
  colors[i] = col;
  vertices[col].push_back(i);
  for (auto c : edges[i]) {
    dfs(c, 1-col);
  }
}

void p() {
  for (ll i=1; i<=N; i++) {
    cout << ans[i] << " ";
  }
  cout << endl;
}

signed main() {
  cin >> N;
  for (ll i=1; i<=N; i++) {
    mod[i%3].push(i);
  }
  rep(i, N-1) {
    ll x,y;
    cin>>x>>y;
    edges[x].push_back(y);
    edges[y].push_back(x);
  }
  dfs(1, 0);
  // cout << "col 0 ->";
  // for (auto i : vertices[0])
  //   cout << i << " ";
  // cout << "col 1->";
  // for (auto i : vertices[1])
  //   cout << i << " ";
  // cout << endl;
  // printf("mod 0->%ld 1->%ld 2->%ld\n", mod[0].size(), mod[1].size(), mod[2].size());

  if (vertices[0].size() <= mod[0].size()) {
    // 1側を 1,2 で埋める
    // 残りを0にする
    // cout << "A" << endl;
    for (auto i : vertices[1]) {
      if      (!mod[1].empty()) { ans[i] = mod[1].front(); mod[1].pop(); }
      else if (!mod[2].empty()) { ans[i] = mod[2].front(); mod[2].pop(); }
    }
    for (ll i=1; i<=N; i++) {
      if (ans[i] == -1) { ans[i] = mod[0].front(); mod[0].pop(); }
    }
    p();
    return 0;
  }

  if (vertices[1].size() <= mod[0].size()) {
    // 0側を 1,2 で埋める
    // 残りを0にする
    // cout << "B" << endl;
    for (auto i : vertices[0]) {
      if      (!mod[1].empty()) { ans[i] = mod[1].front(); mod[1].pop(); }
      else if (!mod[2].empty()) { ans[i] = mod[2].front(); mod[2].pop(); }
    }
    for (ll i=1; i<=N; i++) {
      if (ans[i] == -1) { ans[i] = mod[0].front(); mod[0].pop(); }
    }
    p();
    return 0;
  }

  if (vertices[0].size() >= mod[1].size() && vertices[1].size() >= mod[2].size()){
    // 0側を1で埋める、1側を2で埋める
    // 残りを0にする
    // cout << "C" << endl;
    for (auto i : vertices[0]) {
      if      (!mod[1].empty()) { ans[i] = mod[1].front(); mod[1].pop(); }
    }
    for (auto i : vertices[1]) {
      if      (!mod[2].empty()) { ans[i] = mod[2].front(); mod[2].pop(); }
    }
    for (ll i=1; i<=N; i++) {
      if (ans[i] == -1) { ans[i] = mod[0].front(); mod[0].pop(); }
    }
    p();
    return 0;
  }

  if (vertices[0].size() >= mod[2].size() && vertices[1].size() >= mod[1].size()){
    // 0側を2で埋める、1側を1で埋める
    // 残りを0にする
    // cout << "D" << endl;
    for (auto i : vertices[0]) {
      if      (!mod[2].empty()) { ans[i] = mod[2].front(); mod[2].pop(); }
    }
    for (auto i : vertices[1]) {
      if      (!mod[1].empty()) { ans[i] = mod[1].front(); mod[1].pop(); }
    }
    for (ll i=1; i<=N; i++) {
      if (ans[i] == -1) { ans[i] = mod[0].front(); mod[0].pop(); }
    }
    p();
    return 0;
  }

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


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

using namespace std;

typedef long long ll;
typedef pair<long,long> pl;
typedef pair<ll,ll> pll;
typedef vector<long> vl;
typedef vector<bool> vb;
typedef vector<ll> vll;
typedef vector<vl> vvl;
typedef vector<vb> vvb;
typedef vector<vll> vvll;
typedef vector<pll> vpll;
typedef vector<string> vs;

#define FOR(i,a,b) for(long long i=a;i<b;++i)
#define REV(i,a,b) for(long long i=a;i>=b;i--)
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define tc ll t;cin>>t;while(t--)
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define coutv(v) for(auto it: (v))cout<<it<<" ";newl;
#define cout2d(v) for(auto it: (v)) {for(auto j:it) cout<<j<<" ";newl;}
#define cinv(v,n) vll (v)(n);FOR(i,0,(n)){cin>>v[i];}
#define cinvg(v,n) (v).resize(n);FOR(i,0,(n)){cin>>v[i];}
#define cin2d(v,n,m) vvll (v)(n,vll(m,0));FOR(i,0,n){FOR(j,0,m){cin>>v[i][j];}}
#define cin2dg(v,n,m) (v).resize(n,vll(m));FOR(i,0,n){FOR(j,0,m){cin>>v[i][j];}}
#define newl cout<<"\n"
#define mod 1000000007

int main()
{
  io;
  ll x,h=0;
  cin>>x;
  h+=1000*(x/500);
  x%=500;
  h+=5*(x/5);
  cout<<h;
  return 0;
}

Measured memory_bytes: 256
n = int(input())
a = [('a',int(input())) for _ in range(n)]
b = [('b',int(input()))for _ in range(n)]
ab = sorted(a+b, key=lambda x: x[1])
m = []
count = 0
for k,i in ab:
    if k == 'a':
        if count < 0:
            m.append(-count)
        count += 1
    else:
        if count > 0:
            m.append(count)
        count -= 1
ans = 1
for mm in m:
    ans *= mm
    ans %= 10**9+7
print(ans)


Measured memory_bytes: 30272
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <unordered_map>

using namespace std;
using ll = long long;

void _cin(){} template <class Head, class... Tail> void _cin(Head&& head, Tail&&... tail){ cin >> head; _cin(forward<Tail>(tail)...); }
void _cout(){ cout << "\n"; } template <class Head, class... Tail> void _cout(Head&& head, Tail&&... tail){ cout << head; _cout(forward<Tail>(tail)...); }
int gcd(int a, int b){ return (b == 0) ? a : gcd(b, a % b); }

#define Sq(x) (x)*(x)
#define For(i, n) for(int i = 0; i < (n); i ++)
#define Rep(n) For(_, n)
#define Range(c) c.begin(), c.end()
#define RevRange(c) c.rbegin(), c.rend()
#define Contains(c, x) (find(Range(c), x) != c.end())
#define Search(rb, re, x) distance(rb, find(rb, re, x))
#define Sort(a) sort(Range(a))
#define DeSort(a) sort(RevRange(a))
#define Reverse(c) reverse(Range(c))
#define Unique(a) a.erase(unique(Range(a)), a.end())
#define Vec2(T, n, m, xs) vector<vector<T>> xs(n, vector<T>(m))
#define Sum(a) accumulate(Range(a), 0)
#define Cusum(T, xs, sxs) vector<T> sxs(xs.size()+1); For(i, (int)xs.size()) sxs[i+1] = sxs[i] + xs[i]
#define Cin(T, ...) T __VA_ARGS__; _cin(__VA_ARGS__)
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i]
#define Cins2(T, n, xs, ys) vector<T> xs(n), ys(n); For(i, n) cin >> xs[i] >> ys[i]
#define Cins3(T, n, xs, ys, zs) vector<T> xs(n), ys(n), zs(n); For(i, n) cin >> xs[i] >> ys[i] >> zs[i]
#define Cinss(T, n, m, xs) Vec2(T, n, m, xs); For(i, n) For(j, m) cin >> xs[i][j]
#define Cinm(T, n, map) unordered_map<T, int> map; Rep(n){ Cin(T, x); map[x] ++; }
#define Cout(...) _cout(__VA_ARGS__)
#define Couts(xs) for(const auto &e : xs) cout << e << " "; cout << "\n"
#define Coutyn(cond) Cout((cond) ? "yes" : "no")
#define CoutYn(cond) Cout((cond) ? "Yes" : "No")
#define CoutYN(cond) Cout((cond) ? "YES" : "NO")

// constexpr int MOD = 1e9+7;

int main(){
    Cin(string, s);
    int n = s.size();
    int a = 0;
    for(const auto &c : s){
        if(c == 'o') a ++;
    }
    CoutYN(15-n + a >= 8);
}


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

int main(){
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  
  int s = a/d;
  if (a%d != 0) s++;
  int t = c/b;
  if (c%b != 0) t++;
  if (t <= s) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 3636
/**
 *    author: apurba_debnath
**/
#include <bits/stdc++.h>


#define ll long long
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;


using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    double n;
    cin >> n;
    cout << ceil(n/2);

    return 0;
}


Measured memory_bytes: 3808
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;

namespace AtTest._500problems
{
    class CF2016FinalB
    {
        static void Main(string[] args)
        {
            Method(args);
            ReadLine();
        }

        static void Method(string[] args)
        {
            double[][] xys = new double[3][];
            for (int i = 0; i < 3; i++)
            {
                xys[i] = ReadDoubles();
            }
            double[] ls = new double[3];
            for(int i = 0; i < 3; i++)
            {
                double x1 = xys[i][0];
                double y1 = xys[i][1];
                double x2 = xys[(i+1)%3][0];
                double y2 = xys[(i+1)%3][1];
                ls[i] = Sqrt(Pow(x1 - x2, 2) + Pow(y1 - y2, 2));
            }
            double[] tans = new double[3];
            for (int i = 0; i < 3; i++)
            {
                double a = ls[(i + 2) % 3];
                double b = ls[i % 3];
                double c = ls[(i + 1) % 3];
                tans[i] = Sqrt(4 * a * b / ((a + b) * (a + b) - c * c) - 1);
            }
            double res = 0;
            for(int i = 0; i < 3; i++)
            {
                res = Max(res, ls[i] / (1 / tans[i] + 2 + 1 / tans[(i + 1) % 3]));
            }
            WriteLine(res);
        }

        private static string Read() { return ReadLine(); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
    }
}


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

using namespace std;

int main(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    int te=0,tw=0,e=0,w=0;
    for(int i=0;i<n;i++){
        if(s[i]=='E'){
            te++;
        }
        else{
            tw++;
        }
    }
    int ans=n;
    for(int i=0;i<n;i++){
        if(s[i]=='E'){
            ans=min(ans,w+te-e-1);
            ++e;
        }
        else{
            ans=min(ans,w+te-e);
            ++w;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3908
# スペース区切りの整数の入力
N, K = map(int, input().split())
S = str(input())

for i in range(N):
  if i==K-1:
    if S[i]=="A":
      print("a",end="")
    if S[i]=="B":
      print("b",end="")
    if S[i]=="C":
      print("c",end="")
  else:
    print(S[i],end="")

Measured memory_bytes: 3064
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#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 ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

int main() {
    ll n, a, b;
    cin >> n >> a >> b;
    if (a % 2 == b % 2){
        cout << (b - a) / 2 << endl;
        return 0;
    }
    ll ans1 = a + (b - a - 1) / 2;
    ll ans2 = (n + 1 - b) + (b - a - 1) / 2;
    ll ans = min(ans1, ans2);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Text;
using System.Collections.Generic;
using System.Collections;
using static System.Math;
using System.Linq;
using static System.Array;

namespace ConsoleApp2
{
    class Program
    {

        static long N;
        static long M;
        static long X;
        static long[][] book;

        static void Main(string[] args)
        {
            //var N = long.Parse(Console.ReadLine());
            var NMX = Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();
            N = NMX[0];
            M = NMX[1];
            X = NMX[2];

            var A = Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToList();
            A.Insert(0, 0);
            A.ToArray();
            var B = Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToList();
            B.Insert(0, 0);

            var cumB = new long[M+1];
            cumB[0] = B[0];
            for (int i = 1; i <= M; i++)
            {
                cumB[i] += B[i]+ cumB[i-1];
            }

            var sum = 0L;
            var BP = M;

            var ans = 0L;
            for (int i = 0; i <= N; i++)
            {
                sum += A[i];

                for (; BP > 0; BP--)
                {
                    if (sum + cumB[BP] <= X)
                    {
                        break;
                    }
                }

                if (sum + cumB[BP] <= X)
                {
                    ans = Max(ans, i + BP);
                }
                
            }

            Console.WriteLine(ans);
        }


    }

}


Measured memory_bytes: 71416
// 2020-08-04 17:10:17
#include <bits/stdc++.h>
using namespace std;

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

  int n, r;
  cin >> n >> r;

  (n < 10) ? cout << r + (100 * (10 - n)) << endl : cout << r << endl;
  
  return 0;
}

Measured memory_bytes: 3620
import java.io._
import java.util.StringTokenizer

import scala.collection.mutable
import scala.util.Sorting
import math.{abs, max, min}
import scala.collection.mutable.{ArrayBuffer, ListBuffer}
import scala.reflect.ClassTag

object Main {
  val MOD = 1000000007
  val out = new PrintWriter(System.out)

  def solve(): Unit = {
    val sc = new InputReader(System.in)
    val N = sc.nextInt()
    val S = map(N)(_ => sc.nextInt())
    val mods = Array.ofDim[Int](10)
    rep(N)(i => mods(S(i) % 10) += 1)
    val sum = S.sum
    val ans = if (sum % 10 != 0) sum
    else if (mods(0) == N) 0
    else {
      val ms = (S filter (v => v % 10 != 0)).min
      sum - ms
    }

    out.println(ans)
  }


  def main(args: Array[String]): Unit = {
    solve()
    out.flush()
  }


  class InputReader(val stream: InputStream) {
    private val reader = new BufferedReader(new InputStreamReader(stream), 32768)
    private var tokenizer: StringTokenizer = null

    def next(): String = {
      while (tokenizer == null || !tokenizer.hasMoreTokens)
        tokenizer = new StringTokenizer(reader.readLine)
      tokenizer.nextToken
    }

    def nextInt(): Int = next().toInt
    def nextLong(): Long = next().toLong
    def nextChar(): Char = next().charAt(0)
  }
  def rep(n: Int)(f: Int => Unit): Unit = {
    var i = 0
    while(i < n) { f(i); i += 1 }
  }
  def rep_r(n: Int)(f: Int => Unit): Unit = {
    var i = n - 1
    while(i >= 0) { f(i); i -= 1 }
  }

  def map[@specialized A: ClassTag](n: Int)(f: Int => A): Array[A] = {
    val res = Array.ofDim[A](n)
    rep(n)(i => res(i) = f(i))
    res
  }

  implicit class ArrayOpts[A](val as: Array[A]) extends AnyVal {
    // todo Orderingだとboxing発生するので自作Orderを用意したい
    def maxByOpt[B: Ordering](f: A => B): Option[A] = {
      if (as.nonEmpty) Some(as.maxBy(f)) else None
    }

    def grpBy[K](f: A => K): mutable.Map[K, ArrayBuffer[A]] = {
      val map = mutable.Map.empty[K, ArrayBuffer[A]]
      rep(as.length)(i => map.getOrElseUpdate(f(as(i)), ArrayBuffer()) += as(i))
      map
    }

    def sumBy[B](f: A => B)(implicit num: Numeric[B]): B = {
      var sum = num.zero
      rep(as.length)(i => sum = num.plus(sum, f(as(i))))
      sum
    }

    def minByEx[B](f: A => B, ixRange: Range = as.indices)(implicit cmp: Ordering[B]): (A, B) = {
      limit(f, ixRange)(cmp.lt)
    }

    def maxByEx[B](f: A => B, ixRange: Range = as.indices)(implicit cmp: Ordering[B]): (A, B) = {
      limit(f, ixRange)(cmp.gt)
    }

    private def limit[B](f: A => B, ixRange: Range)(cmp: (B, B) => Boolean): (A, B) = {
      var limA = as(ixRange.head)
      var limB = f(limA)

      for (i <- ixRange.tail) {
        val a = as(i)
        val b = f(a)
        if (cmp(b, limB)) {
          limA = a
          limB = b
        }
      }
      (limA, limB)
    }
  }

  implicit class IterableOpts[A](val as: Iterable[A]) extends AnyVal {
    def sumBy[B](f: A => B)(implicit num: Numeric[B]): B = {
      as.foldLeft(num.zero)((acc, a) => num.plus(acc, f(a)))
    }
  }
}


Measured memory_bytes: 27220
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;

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

	int a, b, c;
	cin >> a >> b >> c;
	cout << a * b / 2 << "\n";
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define printVec(v) printf("{"); for (const auto& i : v) { std::cout << i << ", "; } printf("}\n");
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; }
using namespace std;
using P = pair<int,int>;
using ll = long long;
const ll INF = 1LL<<60;
const double PI = 3.1415926535897932;
const int MOD = 1e9 + 7;

//cin.tie(0);ios::sync_with_stdio(false);
int main() {
  int n, m;
  cin >> n >> m;
  vector<ll> a(n);
  rep (i, n) cin >> a[i];
  sort(a.begin(), a.end());

  vector<pair<ll, ll>> vpi;
  rep (i, m) {
    int b, c;
    cin >> b >> c;
    vpi.push_back(make_pair(c, b));
  }

  sort(vpi.rbegin(), vpi.rend());
 
  int i = 0;
  ll ans = 0;
  bool ok = true;
  for (auto v : vpi) {
    if (ok) {
      int j = upper_bound(a.begin() + i, a.end(), v.first) - a.begin();
      j = j - i;
      if (j == 0) {
	ok = false;
      } else {
	if (j <= v.second) {
	  ans += v.first * j;
	  i += j;
	} else {
	  ans += v.first * v.second;
	  i += v.second;
	}
      }
    }
  }
  ans += accumulate(a.begin() + i, a.end(), 0LL);

  cout << ans << endl;
  return 0;
}


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

#define ll long long

#define ff first
#define ss second
bool comp(ll a,ll b){
    return a > b;
}

bool check(vector<ll> &a,ll k){
    ll n = a.size();
    
    for(ll i=0;i<n-1;i+=2){
        ll x = max(a[i],a[i+1]);
        k-=x;
        if(k<0) return false;
    }
    
    if(n&1){
        k-= a[n-1];
    }
    if(k<0) return false;
    return true;
    
}

void solve()
{
   ll n,a,b;cin>>n>>a>>b;
   
   ll x = n/(a+b);
   
   ll ans = x*a;
   x = n%(a+b);
   
   if(x<=a)
        ans += x;
    else    ans += a;
    
    cout<<ans<<endl;
   
}

int main(){
    
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // ll t;cin>>t;while(t--)
        solve();
    
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt(); in.nextLine();
		char[][] guy = new char[n][n];
		char[][] otherguy = new char[m][m];
		for( int i = 0; i < n; i++ ) {
			String temp = in.nextLine();
			for( int j = 0; j < n; j++ ) {
				guy[i][j] = temp.charAt(j);
			}
		}
		for( int i = 0; i < m; i++ ) {
			String temp = in.nextLine();
			for( int j = 0; j < m; j++ ) {
				otherguy[i][j] = temp.charAt(j);
			}
		}

		String ans = "No";	
		if(n!=m) {
			for( int i = 0; i < n-m; i++ ) {
				if( ans.equals("Yes") ) break;
				for( int j = 0; j < n-m; j++ ) {
					//System.out.printf("%d %d\n",i,j);
					if( guy[i][j] == otherguy[0][0] ) {
						boolean yes = true;
						for( int k = 0; k < m; k++ ) {
							for( int p = 0; p < m; p++ ) {
								if( guy[k+i][p+j] != otherguy[k][p] ) {
									yes = false;
									break;
								}
							}
						}
						if(yes) ans = "Yes";
					}
				}
			}
		} else {
			ans = "Yes";
			for( int i = 0; i < n; i++ ) {
				if( ans.equals("No")) break;
				for( int j = 0; j < n; j++ ) {
					if(guy[i][j] != otherguy[i][j]) {
						ans = "No";
						break;
					}
				}
			}
		}

		System.out.println(ans);
	}

}

Measured memory_bytes: 22740
x, y = map(int, input().split())
if y > x:
  x, y = y, x

def cmb(n, r, p):
  if (r < 0) or (n < r):
    return 0
  r = min(r, n - r)
  return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 6
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

a = (x+y)//3
b = (2*y-x)//3
if (x+y)%3 == 0 and (2*y-x)%3 == 0 and a*b >= 0:
  print(cmb(a, b, p))
else:
  print(0)


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

using namespace std;
using ll =long long;
typedef pair<int,int> P;
#define SORT(a) sort((a).begin(),(a).end())
#define REV(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
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; }

void coY() {cout <<"Yes"<<endl;}
void coN(){cout <<"No"<<endl;}
 
//Write From this Line

//const ll mod = 1e9+7;
//const ll mod = 998244353;
int main()
{
	int n;
	cin >> n;
	vector<int> a(n+1);
	rep(i, n+1)cin>>a[i];
	vector<int> b(n);
	rep(i, n)cin>>b[i];

	ll ans = 0;
	rep(i,n){
		// 勇者 i が倒す数
		ll m = min(b[i],a[i]);
		b[i] -= m;
		ans += m;
		m = min(b[i],a[i+1]);
		a[i+1] -= m;
		ans += m;
	}
	cout << ans << endl;
}


Measured memory_bytes: 3960
#include<bits/stdc++.h>
using namespace std;
inline void rd(int &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(int x){
  char f[10];
  int m=0, s=0;
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
int N;
int A[100000];
int res[100000];
int main(){
  int i, x;
  rd(N);
  {
    int Lj4PdHRW;
    for(Lj4PdHRW=0;Lj4PdHRW<N;Lj4PdHRW++){
      rd(A[Lj4PdHRW]);
    }
  }
  for(i=1;i<N;i++){
    res[i] = A[i-1] - res[i-1];
  }
  x = (A[N-1] - res[N-1]) / 2;
  for(i=0;i<N;i++){
    if(i%2==0){
      res[i]+=x;
    }
    else{
      res[i]-=x;
    }
  }
  {
    int KL2GvlyY;
    if(N==0){
      putchar_unlocked('\n');
    }
    else{
      for(KL2GvlyY=0;KL2GvlyY<N-1;KL2GvlyY++){
        wt_L(2*res[KL2GvlyY]);
        wt_L(' ');
      }
      wt_L(2*res[KL2GvlyY]);
      wt_L('\n');
    }
  }
  return 0;
}
// cLay varsion 20190708-1

// --- original code ---
// int N, A[1d5];
// int res[1d5];
// {
//   int i, x;
// 
//   rd(N,A(N));
//   rep(i,1,N) res[i] = A[i-1] - res[i-1];
// 
//   x = (A[N-1] - res[N-1]) / 2;
//   rep(i,N) res[i] if[i%2==0, +=, -=] x;
// 
//   wt(2res(N));
// }


Measured memory_bytes: 2048