akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

// c++11
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>

#define mp make_pair
#define mt make_tuple
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

const int INF = 1 << 29;
const ll LL_INF = 1LL << 60;
const double EPS = 1e-9;
const ll MOD = 1000000007;

const int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
int N;
vector<ll> X;
ll result;
int main()
{
    cin >> N;
    X.resize(N);
    for (auto &val : X)
    {
        cin >> val;
    }
    stack<ll> positions;
    result = 1;
    for (int i = 0; i < N; i++)
    {
        positions.emplace(X[i]);
        while (not positions.empty())
        {
            ll p = positions.top();
            int size = positions.size();
            if (2 * size - 1 <= p)
            {
                break;
            }
            else
            {
                positions.pop();
                result *= size;
                result %= MOD;
            }
        }
    }
    int size = positions.size();
    for (int i = 1; i <= size; i++)
    {
        result *= i;
        result %= MOD;
    }

    cout << result << endl;
    return 0;
}


Measured memory_bytes: 1792
#include <stdio.h>
 
int main()
{
  int N, Ndiv, NMin, NMax;
  
  scanf("%d", &N);
  Ndiv = (100 * N) / 108;
  NMin = Ndiv * 108 / 100;
  NMax = (Ndiv + 1) * 108 / 100;
 
  if (N == NMin) {
    printf("%d", Ndiv);
  } else if (N == NMax) {
    printf("%d", Ndiv + 1);
  } else {
    printf (":(");
  }
  
  return 0;
}

Measured memory_bytes: 128
#include <stdio.h>

int main()
{
	// 変数定義
	int iPieceNum;						// 駒の数
	int aiPiecePosition[100+1] = { 0 };	// 各駒の位置
	int aiBoard[2019+1] = { 0 };		// ボード全体の駒の配置
	int iOperatingNum;					// 操作回数
	int iOperatingPiece;				// 操作する駒
	int iPrePosition;					// 操作前の駒の位置
	int iCount;

	// 変数初期化

	// 入力：駒の数
	scanf("%d", &iPieceNum);

	// 入力：駒の位置
	for (iCount = 1; iCount <= iPieceNum; iCount++)
	{
		scanf("%d", &aiPiecePosition[iCount]);
		aiBoard[aiPiecePosition[iCount]] = iCount;
	}

	// 入力：操作回数
	scanf("%d", &iOperatingNum);

	// 1回ずつ駒を操作する
	for (iCount = 0; iCount < iOperatingNum; iCount++)
	{
		// 入力：操作する駒
		scanf("%d", &iOperatingPiece);

		// 操作前の駒の位置を代入
		iPrePosition = aiPiecePosition[iOperatingPiece];

		// 駒がゴールにいるときはそのまま
		if (iPrePosition == 2019)
		{

		}
		// 次のマスに駒がいるときはそのまま
		else if (aiBoard[iPrePosition + 1] != 0)
		{

		}
		// 次のマスが空いていれば1進める
		else
		{
			// 盤面の配列を更新
			aiBoard[iPrePosition] = 0;
			aiBoard[iPrePosition + 1] = iOperatingPiece;

			// 駒の位置の配列を更新
			aiPiecePosition[iOperatingPiece]++;
		}
	}

	// 出力：駒の位置
	for (iCount = 1; iCount <= iPieceNum; iCount++)
	{
		printf("%d\n", aiPiecePosition[iCount]);
	}

	return 0;
}


Measured memory_bytes: 2104
#!/usr/bin/env python3

def main():
    N,X = map(int, input().split())
    Ls =  [int(s) for s in input().split()]
    range = 0
    count = 1
    for l in Ls:
        range += l
        if range > X:
            break
        count += 1
    print(count)

if __name__ == "__main__":
    main()


Measured memory_bytes: 2940
#include <iostream>
#include <ios>
#include <iomanip>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <utility>
#include <typeinfo>
using namespace std;

#define MOD 1000000007
#define INF 1e9+7
#define INF_LONG 1e18
#define rep(i, n) for(int i=0; i<n; ++i)
#define rrep(i, m, n) for(int i=m; i<n; ++i)
typedef long long ll;

#define MAX_N 200000
#define MAX_M 100000
#define MAX_V 100
#define MAX_E 100
#define MAX_Q 100000

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};

int ddx[] = {-1, 0, 1, 0, -1, 1, -1, 1};
int ddy[] = {0, -1, 0, 1, 1, 1, -1, -1};

ll gcd(ll x, ll y) {
  if(y==0) return x;
  else return gcd(y, x%y);
}

ll lcm(ll x, ll y) {
  return (x*y)/gcd(x, y);
}

//--------------------------

ll f[MAX_N];
ll a[MAX_N];

int main() {

  ll n;
  cin >> n;
  rep(i, n-1) {
    cin >> a[i];
    ++f[a[i]-1];
  }

  rep(i, n) {
    cout << f[i] << endl;
  }

  return 0;
}


Measured memory_bytes: 6644
n, m = map(int, input().split())
A = list(map(int, input().split()))
A = map(lambda x: x * (-1), A)
A = sorted(A)

from heapq import heappush, heappop

for _ in range(m):
    x = heappop(A)
    heappush(A, (-1*x)//2*(-1))

print(sum(A)*(-1))


Measured memory_bytes: 64236
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=1000000007,MAX=100005,INF=1<<30;

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N;cin>>N;
    vector<ll> A(N);
    for(int i=0;i<N;i++) cin>>A[i];
    sort(all(A));
    reverse(all(A));
    
    if(N==1){
        cout<<A[0]<<endl;
    }else if(N==2){
        cout<<A[0]+A[1]-1<<endl;
    }else if(N==3){
        cout<<A[0]+A[1]+A[2]-3<<endl;
    }else if(N==4){
        if(A[0]==2) cout<<4<<endl;
        else if(A[1]==2) cout<<A[0]+1<<endl;
        else if(A[2]==2) cout<<A[0]+A[1]-1<<endl;
        else cout<<A[0]+A[1]+A[2]-3+max(A[3]-3,0LL)<<endl;
    }else{
        if(A[0]==2) cout<<4<<endl;
        else if(A[1]==2){
            if(A[0]==3) cout<<5<<endl;
            else cout<<A[0]+1<<endl;
        }else if(A[2]==2){
            cout<<A[0]+A[1]-1<<endl;
        }else if(A[3]==2){
            cout<<A[0]+A[1]+A[2]-3<<endl;
        }else{
            if(A[4]==2) cout<<A[0]+A[1]+A[2]+A[3]-6<<endl;
            else if(A[4]==3){
                if(A[0]==3) cout<<7<<endl;
                else if(A[0]==4&&A[1]==3) cout<<8<<endl;
                else cout<<A[0]+A[1]+A[2]+A[3]-6<<endl;
            }else{
                cout<<A[0]+A[1]+A[2]+A[3]+A[4]-10<<endl;
            }
        }
    }
    
}




Measured memory_bytes: 3224
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn],pre[maxn],sa[maxn];
int main()
{
    int n;
    cin>>n;
    for (int i = 1;i <= n;i ++)
        cin>>a[i];

    for (int i = 1;i <= n;i ++)
        pre[i] = max(pre[i-1],a[i]);
    for (int i = n;i;i --)
        sa[i] = max(sa[i +1],a[i]);
    for (int i = 1;i <= n;i ++)
        cout<<max(pre[i-1],sa[i+1])<<'\n';
    return 0;
}


Measured memory_bytes: 3968
fun main(args:Array<String>):Unit {
    while(true){
        val arg = readLine()!!.split(' ').map(String::toInt)
        if (arg.all{it == 0}) return
        val (n, m, l) = arg.take(3)
        val (k, a, h) = arg.takeLast(3)
        val minRouteWholeCity = Array(n){Array(n){Int.MAX_VALUE}}
        val cityWithFreezer = ((if (l != 0) readLine()!!.split(' ').map(String::toInt) else {readLine(); listOf()}) + a + h).sorted()
        val home = cityWithFreezer.indexOfFirst { it == a }
        val hospital = cityWithFreezer.indexOfFirst { it == h }
        repeat(k){
            val (x, y, t) = readLine()!!.split(' ').map(String::toInt)
            minRouteWholeCity[x][y] = t
            minRouteWholeCity[y][x] = t
        }
        for (mid in 0 until n) for (from in 0 until n) for (to in 0 until n){
            if (minRouteWholeCity[from][to] - minRouteWholeCity[from][mid] > minRouteWholeCity[mid][to]){
                minRouteWholeCity[from][to] = minRouteWholeCity[from][mid] + minRouteWholeCity[mid][to]
                minRouteWholeCity[to][from] = minRouteWholeCity[from][to]
            }
        }
        val minWithFreezer = cityWithFreezer.map{ from ->
            cityWithFreezer.map{to ->
                if (minRouteWholeCity[from][to] > m)
                    Int.MAX_VALUE
                else
                    minRouteWholeCity[from][to]
            }.toTypedArray()}.toTypedArray()
        for (mid in 0 until minWithFreezer.size) for (from in 0 until minWithFreezer.size) for (to in 0 until minWithFreezer.size){
            if (minWithFreezer[from][to] - minWithFreezer[from][mid] > minWithFreezer[mid][to]){
                minWithFreezer[from][to] = minWithFreezer[from][mid] + minWithFreezer[mid][to]
                minWithFreezer[to][from] = minWithFreezer[from][to]
            }
        }
        println(if (minWithFreezer[home][hospital] == Int.MAX_VALUE) "Help!" else if (minWithFreezer[home][hospital] > m) (2 * minWithFreezer[home][hospital] - m) else minWithFreezer[home][hospital])
    }
}


Measured memory_bytes: 91804
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
	int N;
	string S;
	cin >> N >> S;
 
	map<string, int> mp;
	for( int i = 0; i <= 9; i++ ) {
		char c = (char)('0' + i);
		int n = S.find( c );
		if( n == string::npos ) continue;
		for( int j = 0; j <= 9; j++ ) {
			char c1 = (char)('0' + j);
			int n1 = S.find( c1, n + 1 );
			if( n1 == string::npos ) continue;
			for( int k = 0; k <= 9; k++ ) {
				char c2 = (char)('0' + k);
				int n2 = S.find( c2, n1 + 1 );
				if( n2 == string::npos ) continue;
				string s;
				s += c;
				s += c1;
				s += c2;
				mp[s]++;
			}
		}
	}
	int ans = mp.size();
 
	cout << ans << endl;
}


Measured memory_bytes: 384
#include<iostream>
#include<vector>
#include<sstream>
#include<string>
#include<numeric>
#include <algorithm>
#include<math.h>
#include<cstdio>
#include<string.h>




using namespace std;
typedef long long ll;
struct point{
  int x;
  int y;

};
int gcd(int m, int n )
{
	// 引数に０がある場合は０を返す
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
	// ユークリッドの方法
	while( m != n )
	{
		if ( m > n ) m = m - n;
		else         n = n - m;
	}
	return m;
}//gcd
int lcm( int m, int n )
{
	// 引数に０がある場合は０を返す
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
	return ((m / gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}//lcm
int input(){
  int x;
  cin>>x;
  return x;
}

int moji(char in)
{
    int ans = (int)in-(int)'a';
    if((ans < 0) || (ans > 25)){
        ans = 26;
    }
    return ans;
}
const int VV=10;//場合に応じてVVの値のみ変更する必要あり
//dijkstra(s)sがスタート地点でそこからの最短距離を配列dで表す。正の重みのみ使用可能
int cost[VV][VV];
int d[VV];
bool used[VV];
void dijkstra(int s){
  fill(d,d+VV,100000);
  fill(used,used+VV,false);
  d[s]=0;
  while(true){
    int v=-1;
    for(int u=0;u<VV;u++){
      if(!used[u]&&(v==-1||d[u]<d[v]))v=u;
    }
    if(v==-1)break;
    used[v]=true;
    for(int u=0;u<VV;u++){
      d[u]=min(d[u],d[v]+cost[v][u]);
    }
  }

}

int compare_int(const void *a, const void *b)//qsort(quick sort利用時に使用)
{
    return *(int*)a - *(int*)b;
}

int binary_searchh(long long x,long long k[],int n){
  int l=0;
  int r=n;
  while(r-l>=1){
    int i=(l+r)/2;
    if(k[i]==x)return i;
    else if(k[i]<x)l=i+1;
    else r=i;
  }
  return -1;
}




int main(){
  long N,P;
  cin>>N>>P;
  long a[(int)sqrt(P)];
  if(N!=1){
  for(int i=0;i<sqrt(P);i++){
    a[i]=0;
  }
  long long tmp=P;
  for(int i=2;i<sqrt(P);i++){
    if(tmp==1){
      break;
    }

    while(tmp%i==0){
      tmp/=i;
      a[i]++;
    }

  }
  int sum=1;
  for(int i=0;i<sqrt(P);i++){
    while(a[i]>=N){
      sum*=i;
      a[i]-=N;
    }
  }
  cout<<sum<<endl;}
  else{
    cout<<P<<endl;
  }

  


  

  



}


  
  


  




Measured memory_bytes: 8064
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val s = List.fill(sc.nextInt())(sc.nextInt()).sorted
  val max = s.sum match {
    case sum if sum % 10 != 0 => sum
    case sum => s.find(_ % 10 != 0).map(sum - _).getOrElse(0)
  }
  println(max)
}


Measured memory_bytes: 55616
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define REP(i, d, n) for(int i=(d); i<(n); ++i)
#define all(v) v.begin(), v.end()
using ll = long long;
using P = pair<int, int>;

int main() {

    int n;
    cin >> n;
    vector<int> w(n);
    int sum = 0;
    rep(i, n){
        cin >> w[i];
        sum += w[i];
    }

    int ans = INT_MAX;
    int tmp = 0;
    rep(i, n){
        tmp += w[i];
        ans = min(ans, abs((sum-2*tmp)));
    }
    cout << ans << endl;

    return 0;
}

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

using namespace std;

int main() {
	static long long int n , a[1000010], b[1000010], k;
	cin >> n >> k;
	fill(b , b + n , 10000000000);
	cin >> a[0];
	b[0] = 0;
	for (long long int i = 1; i < n; i++){
		cin >> a[i];
		for (long long int j = 1; j <= k; j++){
			if (i - j < 0){
				break;
			}
			b[i] = min (b[i] , b[i - j] + abs(a[i - j] - a[i]));
		}
	}
	cout << b[n - 1];
}

Measured memory_bytes: 5120
package main

import (
	"fmt"
	"sort"
)

func main() {
	var str string
	var k int
	fmt.Scan(&str, &k)
	mp := make(map[string]int)
	arr := make([]string, 0)
	for i := 0; i < len(str); i++ {
		for j := 1; j <= 5 && i + j <= len(str); j ++ {
			key := str[i:i + j]
			_, ok := mp[key]
			if !ok {
				mp[key] = 1
				arr = append(arr, key)
			}
		}
	}
	sort.Strings(arr)
	fmt.Println(arr[k - 1])
}

Measured memory_bytes: 3712
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cstdint>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

struct MaxFlow {
  struct Edge {
    i64 v, c, f;
  };

  i64 n, s, t;
  vector<vector<i64>> g;
  vector<Edge> es;

  MaxFlow(i64 n, i64 s, i64 t) : n(n), s(s), t(t), g(n + 1) {}
  void add_edge(i64 u, i64 v, i64 c);
  i64 relax();
  i64 max_flow();
};

void MaxFlow::add_edge(i64 u, i64 v, i64 c) {
  g[u].push_back(es.size());
  es.push_back({ v, c, 0 });
  g[v].push_back(es.size());
  es.push_back({ u, 0, 0 });
}

i64 MaxFlow::relax() {
  queue<i64> q;
  vector<i64> route(n + 1, -1);
  q.push(s);
  route[s] = -2;
  while (!q.empty()) {
    i64 u = q.front();
    q.pop();
    for (i64 ei : g[u]) {
      const Edge& e = es[ei];
      if (route[e.v] == -1 && e.c - e.f > 0) {
        q.push(e.v);
        route[e.v] = ei;
        if (e.v == t) goto found;
      }
    }
  }
  return 0;
found:
  i64 mf = 1ll << 62;
  for (i64 u = t; u != s; ) {
    i64 ei = route[u], rei = ei ^ 1;
    const Edge& e = es[ei], &re = es[rei];
    mf = min(mf, e.c - e.f);
    u = re.v;
  }
  for (i64 u = t; u != s; ) {
    i64 ei = route[u], rei = ei ^ 1;
    Edge& e = es[ei], &re = es[rei];
    e.f += mf;
    re.f -= mf;
    u = re.v;
  }
  return mf;
}

i64 MaxFlow::max_flow() {
  i64 f = 0;
  while (true) {
    i64 x = relax();
    cerr << x << endl;
    if (x == 0) break;
    f += x;
  }
  return f;
}

i64 n;
vector<i64> a;
int main() {
  cin >> n;
  read_n(a, n, 1);
  i64 s = 0, t = n + 1;
  MaxFlow mf(n + 2, s, t);
  i64 ofs = 0;
  for (i64 i = 1; i <= n; ++i) {
    ofs += max(i64(0), a[i]);
    // keep
    mf.add_edge(s, i, max(i64(0), -a[i]));
    // break
    mf.add_edge(i, t, max(i64(0), a[i]));
  }
  /*
   * s------>2---/-->t
   * | keep  / break ^
   * |       v       |
   * +---/-->4-------+
  */
  for (i64 i = 1; i <= n; ++i) {
    for (i64 x = 2 * i; x <= n; x += i) {
      mf.add_edge(i, x, 1000000000000);
      cerr << i << '(' << a[i] << ")\t--->\t" 
        << x << '(' << a[x] << ')' << endl;
    }
  }
  i64 ans = ofs - mf.max_flow();
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <numeric>

using namespace std;
typedef long long ll;

int main(){

  string s;
  cin >> s;
  int count = 0;
  for (int i = 0; i < s.size(); i++){
    if(s[i] == 'o'){
      count += 1;
    }
  }
  cout << 700 + 100 * count << endl;

  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner sc =new Scanner(System.in);
		int w =sc.nextInt();
		int n=sc.nextInt();
		int[] values=new int[w];
		for(int i=0;i<values.length;i++){
			values[i]=i+1;
		}
		for(int i=0;i<n;i++){
			String str =sc.next();
			String[] ab=str.split(",");
			int a=Integer.parseInt(ab[0])-1;
			int b=Integer.parseInt(ab[1])-1;
			int c=values[a];
			values[a]=values[b];
			values[b]=c;
		}
		for(int i=0;i<values.length;i++){
			System.out.println(values[i]);
		}
	}
	
}

Measured memory_bytes: 17200
using System;

public class Hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var m1 = long.Parse(line[0]);
        line = Console.ReadLine().Trim().Split(' ');
        var m2 = long.Parse(line[0]);
        Console.WriteLine(m1 == m2 ? 0 : 1);
    }
}


Measured memory_bytes: 11092
#include <iostream>
#include <queue>
#define ll long long
#define pii pair<ll, ll>
#define fst first
#define snd second
using namespace std;

int n;
pii ar[100001]={};
ll lz1, lz2, rs;
priority_queue<pii> pq1;
priority_queue<pii> pq2;

inline ll abbs(ll a) {return ((a < 0) ? -a : a);}

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {cin >> ar[i].fst >> ar[i].snd;}
	pq1.push({ar[0].fst, 0});
	pq2.push({-ar[0].fst, 0});
	for (int i = 1; i < n; i++)
	{
		lz1 -= ar[i].snd - ar[i].fst;
		lz2 -= ar[i-1].snd - ar[i-1].fst;
		//cout<<pq1.top().fst + lz1<<" "<<-(pq2.top().fst + lz2)<<"\n";
		if (ar[i].fst < pq1.top().fst + lz1)
		{
			pq2.push({-(pq1.top().fst + lz1) - lz2, 0});
			pq1.push({ar[i].fst - lz1, 1});
			ll val = pq1.top().fst, ng = 0;
			while (pq1.size() && pq1.top().fst == val)
			{
				ng += pq1.top().snd;
				pq1.pop();
			} 
			if (ng) {pq1.push({val, ng - 1});}
			rs += abbs(-(pq2.top().fst + lz2) - ar[i].fst);
		}
		else if (ar[i].fst > -(pq2.top().fst + lz2))
		{
			pq1.push({-(pq2.top().fst + lz2) - lz1, 0});
			pq2.push({-ar[i].fst - lz2, 1});
			//cout<<"PQ1 INS "<<-(pq2.top().fst + lz2)<<"\n";
			//cout<<"PQ2 INS "<<ar[i].fst<<"\n";
			ll val = pq2.top().fst, ng = 0;
			while (pq2.size() && pq2.top().fst == val)
			{
				ng += pq2.top().snd;
				pq2.pop();
			} 
			if (ng) {pq2.push({val, ng - 1});}
			//cout<<pq1.top().fst + lz1<<" "<<ar[i].fst<<"\n";
			rs += abbs(pq1.top().fst + lz1 - ar[i].fst);
		}
		else
		{
			pq1.push({ar[i].fst - lz1, 0});
			pq2.push({-(ar[i].fst) - lz2, 0});
		}
	}
	cout << rs << "\n";
	return 0;
}

Measured memory_bytes: 5224
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int D = sc.nextInt();
		int X = sc.nextInt();
		
		int[] data = new int[N];
		
		for(int i = 0; i < N; i++) {
			data[i] = sc.nextInt();
		}
		
		int cnt = 0;
		
		for(int i = 0; i < N; i++) {
			int x = 1;
			while(x <= D) {
				cnt++;
				x += data[i];
			}
		}
		
		System.out.println(X + cnt);
		
		sc.close();

	}

}


Measured memory_bytes: 23764
#include<stdio.h>
int main(void){
int n,x;
  scanf("%d%d",&n,&x);
  int l[n];
  for(int i=0;i<n;i++){
	scanf("%d",&l[i]);
  }
  int d[n+1];
  d[0]=0;
  int c=1;
  for(int i=1;i<n+1;i++){
	d[i]=d[i-1]+l[i-1];
    //printf("%d\n",d[i]);
    if(d[i]>x)break;
     c++;
  }
  printf("%d",c);
  return 0;
}

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

using namespace std;

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

    vector<int> B(n-1);

    cin >> B[0];
    int sum = B[0];

    for(i=1; i<n-1; i++){
        cin >> B[i];
        sum += min(B[i],B[i-1]);
    }

    sum += B[n-2];

    cout << sum << endl;

    return 0;
}

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

using namespace std;
using   ll=long long;

#define fast            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

#define endl            "\n"
#define pb              push_back
#define mp              make_pair
#define F               first
#define S               second
#define int             long long int
#define pll                pair<int , int>

#define ALL(v)          v.begin(),v.end()
#define ALLR(v)         v.rbegin(),v.rend()
#define pii             3.14159265358979323
#define inf             LLONG_MAX
#define ones(x)         __builtin_popcount(x)
#define fill(a,b)       memset(a,b,sizeof(a))
#define mod             1000000007
#define hell            998244353

ll mod_pow(ll a,ll b,ll m)
{
    ll res = 1;
    while(b)
    {
        if(b&1)
        {
            res=(res*a) % m;
        }
        a=(a*a) % m;
        b>>=1;
    }
    return res;
}

ll mod_inverse(ll a)
{
    return mod_pow(a , mod-2 , mod);
}

const int maxn = 2e5 + 1;

vector<vector<int>> a(maxn);

int tot;

int vis[maxn];

void dfs(int u) {
	vis[u] = 1;
	
	tot++;
	
	for(auto v : a[u]) {
		if(!vis[v])  {
			dfs(v);
		}
	}
}

void solve()
{
	int n , m;
	
	cin >> n >> m;
	
	for(int i = 0; i < m; ++i) {
		int x , y;
		
		cin >> x >> y;
		
		a[x].pb(y);
		a[y].pb(x);
	}
	
	int ans = 0;
	
	for(int i = 1; i <= n; ++i) {
		if(!vis[i]) {
			tot = 0;
			
			dfs(i);
			
			//cout << i <<" " << tot << endl;
			
			ans = max(ans , tot);
		}
	}
	
	cout << ans;
}

signed main() {
    fast;

    int t = 1;
   
    //cin >> t;

    while(t--) {
        solve();
    }

    return 0;
}


Measured memory_bytes: 21900
fn main() {
    let s = read::<String>();
    let mut v: Vec<char> = s.chars().into_iter().collect();
    let n = v.len();
    let mut ret = 0;
    for i in 1..n {
        if v[i-1] != v[i] { continue; }
        if v[i-1] == '0' {
            v[i] = '1';
        } else {
            v[i] = '0'
        }
        ret += 1;
    }
    println!("{}", ret);
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().parse().ok().unwrap()
}

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

long long int c[101][101]={0};

int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
            scanf("%d",&c[i][j]);
        }
    }
    long long int cost = 0;
    for(int i=0;i<n;++i){
        for(int j=i+1;j<n;++j){
            cost += min(c[i][j], c[j][i]);
        }
    }
    cout << cost << endl;

    return 0;
}


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

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] a = new int[3];
		a[0] = sc.nextInt();
		a[1] = sc.nextInt();
		a[2] = sc.nextInt();
		Arrays.sort(a);
		System.out.println(Math.abs(a[1] - a[0]) + Math.abs(a[2] - a[1]));
	}
}

Measured memory_bytes: 23636
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin>>n;
    vector<int> ans(n);
    
    ans[0] = 0;
    int e;
    cin>>e;
    int h;
    cin>>h;
    ans[1] = abs(h-e);
    for(int i =2; i<n; i++){
        int a;
        cin>>a;
        ans[i] = min(abs(a-e)+ans[i-2],abs(a-h)+ans[i-1]);
        e = h;
        h = a;
    }
    cout<<ans[n-1]<<endl;
    
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n,m;
  cin>>n>>m;
  vector<int>a(n,1);
  set<int>s;
  s.insert(0);
  for(int i=0;i<m;i++)
  {
    int f,t;
    cin>>f>>t;
    f--;
    t--;
    a[f]--;
    a[t]++;
    if(s.count(f))
    {
      s.insert(t);
      if(!a[f])s.erase(f);
    }
  }
  cout<<s.size()<<endl;
  return 0;
}


Measured memory_bytes: 5376
n,l=map(int,input().split())
total=n*(l+(n-1)/2)
min=l+n-1
s=n
for i in range(1,n+1):
  if abs(l+i-1)<min:
    min=abs(l+i-1)
    s=i
    
print(int(total-(l+s-1)))

Measured memory_bytes: 3060
def solve():
  N = int(input())
  B = [int(i) for i in input().split()]
  ans = [0 for i in range(N)]

  for i in range(N - 1, -1, -1):
    v = -1
    for j in range(i + 1):
      if B[j] == j + 1: v = j
    if v == -1: return [ -1 ]
    ans[i] = v + 1
    B.pop(v)
  return ans

print(*solve(), sep='\n')


Measured memory_bytes: 3064
#coding:utf-8
D,G=map(int,input().split(" "))
Comp={}
for i in range(D):
  p,c=map(int,input().split(" "))
  Comp[i]=[p,c]
Min=1000000000
for i in range(2**(D)):
  answer=0
  score=0
  Clear=[]
  for j in range(D):
    if ((i>>j)&1):
      score+=(j+1)*100*Comp[j][0]
      score+=Comp[j][1]
      answer+=Comp[j][0]
      Clear.append(j+1)
  No=D
  Count=0
  while score<G and No>=1:
    if No in Clear or Count==Comp[No-1][0]:
      Count=0
      No-=1
    score+=100*No
    Count+=1
    answer+=1
  Min=min(Min,answer)
print(Min)  

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
struct Fast {
    Fast() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} fast;

long long mod = 1000000007;

long long div(long long a, long long b, long long c) { return b / c - (a - 1) / c; }

void print_binary(long long a) {
    for (int i = 31; i >= 0; i--) {
        cout << (a >> i & 1);
    }
    cout << endl;
}
long long modpow(long long m, long long n) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        long long t = modpow(m, n / 2);
        return t * t;
    } else {
        return modpow(m, n - 1) * m;
    }
}
void yes() {
    cout << "Yes" << endl;
    exit(0);
}
void no() {
    cout << "No" << endl;
    exit(0);
}

int main() {
    long long min = 10000, a, b, c;
    string s;
    cin >> s;
    for (int i = 0; i < s.size() - 2; i++) {
        a = s[i] - '0';
        b = s[i + 1] - '0';
        c = s[i + 2] - '0';
        if (min > abs(753 - a * 100 - b * 10 - c)) {
            min = abs(753 - a * 100 - b * 10 - c);
        }
    }
    cout << min << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <list>
#include <ctime>
#include <complex>
#include <bitset>
#include <tuple>

#define ff first
#define ss second

using namespace std;
using pii=pair<int,int>;
using ll=long long;

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

    string s,t;
    cin>>s>>t;
    t.pop_back();
    if(s==t) cout<<"Yes";
    else cout<<"No";

    return 0;
}


Measured memory_bytes: 3648
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] a = new int[n];
    for(int i = 0; i < n; i++) {
      a[i] = sc.nextInt();
    }
    int ans = Integer.MAX_VALUE;
    for(int t = -100; t <= 100; t++) {
      int c = 0;
      for(int i = 0; i < n; i++) {
        c += ((a[i] - t) * (a[i] - t));
      }
      ans = Math.min(ans, c);
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T,class U> using P = pair<T,U>;
template<class T> using vec = vector<T>;
template<class T> using vvec = vector<vec<T>>;

class BVCC{
private:
    vector<int> ord,low,used;
    vector<vector<int>> g;
    vector<vector<P<int,int>>> bc;
    vector<P<int,int>> tmp;
    int N,K = 0;
public:
    set<int> ap;
    BVCC(int n,vector<vector<int>> v){
        N = n;
        g = v;
        ord = low = vector<int>(N,-1);
        used = vector<int>(N,0);
    }
    void dfs(int now,int prev){
        used[now] = 1;
        ord[now] = K++;
        low[now] = ord[now];
        int cnt = 0;
        for(auto x:g[now]) if(x!=prev){
            if(ord[x]<ord[now]){
                tmp.emplace_back(min(now,x),max(now,x));
            }
            if(!used[x]){
                cnt++;
                dfs(x,now);
                low[now] = min(low[now],low[x]);
                if(low[x]>=ord[now]){
                    if(now!=0) ap.insert(now);
                    bc.push_back({});
                    while(true){
                        P<int,int> e = tmp.back();
                        bc.back().emplace_back(e);
                        tmp.pop_back();
                        if(min(now,x)==e.first && max(now,x)==e.second) break;
                    }
                }
            }else low[now] = min(low[now],ord[x]);
        }
        if(now==0 && cnt>=2) ap.insert(now);
    }
    void decomposition(){
        dfs(0,-1);
    }
};

int N,M;
int main(){
    cin >> N >> M;
    vector<vector<int>> v(N);
    int a,b;
    for(int i=0;i<M;i++){
        cin >> a >> b;
        v[a].push_back(b); v[b].push_back(a);
    }
    BVCC bvcc(N,v);
    bvcc.decomposition();
    for(auto x:bvcc.ap) cout << x << endl;
}


Measured memory_bytes: 6632
N = int(input())
S = [d for d in input()]

tot = S[1:].count('E')
tot_list = [tot]
former_leader = S[0]

for l in range(1, N):
    leader = S[l]
    if (former_leader, leader)  == ('E', 'E'):
        tot -= 1
    if (former_leader, leader)  == ('W', 'W'):
        tot += 1
        
    former_leader = leader  
    tot_list.append(tot)
    
print(min(tot_list))

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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define ALL(x) x.begin(),x.end()
#define EPS (1e-8)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

typedef long long ll;
bool LTE(double a,double b) { return equals(a,b) || a < b; }
bool LT(double a,double b) { return !equals(a,b) && a < b; }

void compute() {

}

int main() {
  ll n,K;
  cin >> n >> K;
  vector<ll> vec(K,0);
  REP(i,1,n+1) ++vec[i%K];
  ll answer = 0;
  rep(i,K) {
    int a = ( K - i ) % K;
    int b = a;
    if( ( a + b ) % K == 0 ) {
      answer += ( vec[a] * vec[b] * vec[i] );
    }
  }
  cout << answer << endl;
  compute();
  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, k, a[15]; 
int main(){
	scanf("%d", &n);
	for(i=1; i<=n; i++){
		scanf("%d", &a[i]);
		m += a[i]; 
	}
	sort(a+1, a+n+1);
	m -= a[n];
	if(a[n] < m) printf("Yes\n");
	else printf("No\n"); 
	return 0; 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
const long long INF = 1LL << 60;
const long long MOD = 1000000007;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i <= (n); ++i)
#define rrep(i, n) for (ll i = (n - 1); i >= 0; --i)
#define perm(c) sort(ALL(c));for(bool c##p=1;c##p;c##p=next_permutation(ALL(c)))
#define ALL(obj) (obj).begin(), (obj).end()
#define pb push_back
#define to_s to_string
#define len(v) (ll)v.size()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define print(x) cout << (x) << '\n'
#define drop(x) cout << (x) << '\n', exit(0)
#define debug(x) cout << #x << ": " << (x) << '\n'
using namespace std;
using ll = long long;
typedef pair<ll, ll> P;
typedef vector<ll> vec;
typedef vector<vector<ll>> vec2;
typedef vector<vector<vector<ll>>> vec3;
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; }
ll devc(ll x, ll y) { return 1 + (x - 1) / y; }



int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);

    string S;
    cin >> S;
    ll N = len(S);
    vec left(N + 1);
    vec right(N + 1);

    rep(i, N) if(S[i] == '<') left[i + 1] = left[i] + 1;
    rrep(i, N) if (S[i] == '>') right[i] = right[i + 1] + 1;

    ll ans = 0;
    rep(i, N + 1) ans += max(left[i], right[i]);
    print(ans);

    return 0;
}

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

int main() {
    ll N; cin >> N;
    vector<ll> A(N+1);
    ll total = 0;
    rep(i, N){
        cin >> A[i+1];
        total += A[i+1];
    }

    vector<ll> ans(N+1);
    ll s = 0;
    for (int i = 2; i <= N-1; i+=2){
        s += A[i];
    }

    ans[1] = total - 2*s;

    for (int i = 2; i <= N; i++){
        ans[i] = A[i-1]*2 - ans[i-1];
    }

    rep(i, N){
        cout << ans[i+1];
        if (i != N-1){
            cout << " ";
        } else {
            cout << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 2944
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
using namespace std;

template<typename T>
ostream& operator << (ostream& os, vector<T>& v){
	rep(i,v.size()){ os << v[i] << (i == v.size() - 1 ? "" : " "); } return os;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& v){
	for(T& x: v){ is >> x; } return is;
}

int main(){
	int a, b;
	cin >> a >> b;

	if(a + b == 15) cout << '+' << endl;
	else if(a * b == 15) cout << '*' << endl;
	else cout << 'x' << endl;
}


Measured memory_bytes: 768
#include<iostream>
#include<cstdio>
#include<ctype.h>
using namespace std;
inline int read(){
	int x=0,f=0;char ch=getchar();
	while(!isdigit(ch))f|=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+(ch^48),ch=getchar();
	return f?-x:x;
}
char x,y;
int main(){
	cin>>x>>y;
	puts(x<y?"<":x>y?">":"=");
	return 0;
}

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

#define pb push_back
#define mp make_pair
#define pf push_front
#define ff first
#define ss second
#define vll vector < ll >
#define vvll vector < vll >
#define vld vector < ld >
#define pll pair < ll,ll >
#define ppll pair < ll, pll > 
#define pld pair < ld,ld > 
#define vpll vector < pll >
#define vpld vector < pld >
#define all(X) X.begin(),X.end()
#define rall(X) X.rbegin(),X.rend()
#define endl "\n"
#define sz(x) ((ll)((x).size()))
vll emptyVector;
const ll MAX = 1e5 + 5;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ld pi = 3.141592653589793238462643383279502884197169399375105;

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " is " << a << endl;
    err(++it, args...);
}

ll binaryExpo(ll x, ll n)
{
	if(n == 0)
		return 1;
	if(n % 2 == 0)
		return binaryExpo((x*x) % MOD, n/2);
	return (x*binaryExpo((x*x) % MOD, n/2)) % MOD;
}

ll gcd(ll a, ll b)
{
	if(b == 0)
		return a;
	return gcd(b, a % b);
}
/*-------------------------------------------		CODE STARTS FROM HERE		------------------------------------------*/


void solve(void)
{
	ll n;
	cin >> n;

	string s;

	while(n){
		ll r = n % 26;
		if(!r)	n -= 26;
		n /= 26;
		char ch = 'a';
		if(!r)
			ch = 'z';
		else
			ch += (r - 1);
		s.pb(ch);
	}

	reverse(all(s));

	cout << s << endl;
	


	
	




}

int main(void)
{
	// ios_base::sync_with_stdio(false);
	// cin.tie(NULL);


	// int t;
	// cin >> t;
	// while(t--)
	{
		solve();
	}


	return 0;
}

Measured memory_bytes: 3632
#include<stdio.h>
#define N 10000
int A[2000001],C[N],B[2000001];
int main()
{
  int i,n;

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

  for(i=0;i<N;i++){
    C[i]=0;
  }
  for(i=1;i<n+1;i++){
    C[A[i]]+=1;
  }
  for(i=1;i<N;i++){
    C[i]+=C[i-1];
  }
  for(i=n+1;i>0;i--){
    B[C[A[i]]]=A[i];
    C[A[i]]-=1;
  }

  for(i=1;i<n;i++){
    printf("%d ",B[i]);
  }
  printf("%d",B[i]);
  printf("\n");
  return 0;
}

Measured memory_bytes: 18316
fun main(args: Array<String>){
    readLine()!!.toInt()
    var inputList = readLine()!!.split(" ").map{ it.toInt() }.toMutableList()
    while (true) {
        inputList.filter { it > 0 }
        inputList.sort()
        val x = inputList[0]
        inputList = inputList.drop(1).map {
            it % x
        }.filter{ it > 0 }.toMutableList()
        inputList.add(x)
        if (inputList.size <= 1) {
            println(x)
            break
        }
    }
}

Measured memory_bytes: 59680
#include<stdio.h>
int main()
{int a,b;
int m,n;
scanf("%d%d",&m,&n);
if(m<n)
{b=m;
m=n;
n=b;
    }
while(n)
{  a=m%n;
   m=n;
   n=a;
}
printf("%d\n",m);
return 0;}


Measured memory_bytes: 2060
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#define MOD 1000000007
typedef long long ll;
using namespace std;

int num[10][10];
bool used[10];
int mi;
string ans;

void solve(string now){
  if(now.size()==9){
    int cost=0;
    int arr[3][3]={};
    for(int i=0;i<3;i++){
      for(int j=0;j<3;j++){
        arr[i][j]=now[i*3+j]-'0';
      }
    }
    for(int i=0;i<3;i++){
      for(int j=0;j<3;j++){
        for(int nx=0;nx<3;nx++){
          for(int ny=0;ny<3;ny++){
            if(nx==i&&ny==j) continue;
            cost+=(num[arr[i][j]][arr[nx][ny]])*(abs(i-nx)+abs(j-ny));
            if(cost>mi) return;
          }
        }
      }
    }

    if(cost<mi){
      mi=cost;
      ans=now;
    }else if(cost==mi){
      if(ans>now) ans=now;
    }
    return;
  }

  for(int i=1;i<=9;i++){
    if(used[i]) continue;
    used[i]=true;
    string next=now;
    next+=(char)('0'+i);
    solve(next);
    used[i]=false;
  }
  return;
}

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

  for(int i=1;i<n;i++){
    num[s[i-1]-'0'][s[i]-'0']++;
  }

  mi=1e9;

  solve("");
  //cout<<mi<<" "<<ans<<endl;
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      cout<<ans[i*3+j];
    }
    cout<<endl;
  }

  return 0;
}



Measured memory_bytes: 3348
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define rep(i,b) for(auto i=0;i<(b);i++)
#define pb push_back
#define sz(c) int((c).size())

bool piicomp(const pii& a, const pii& b)
{
  if (a.first < b.first)
    return true;
  else if (a.first > b.first)
    return false;
  else {
    if (a.second > b.second)
      return true;
    else
      return false;
  }
}

typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
const int maxitem = 1005;
vvpii dp(maxitem, vpii(maxitem, pii(0,0)));

pii rec(int capacity, int i, vi& value, vi& weight)
{
  if (i >= sz(value))
    return pii(0,0);
  if (dp[capacity][i].first != -1)
    return dp[capacity][i];
  if (weight[i] > capacity)
    return dp[capacity][i] = rec(capacity, i+1, value, weight);

  pii tmp = rec(capacity-weight[i], i+1, value, weight);
  return dp[capacity][i] = max(pii(tmp.first+value[i], tmp.second+weight[i]),
                               rec(capacity, i+1, value, weight),
                               piicomp);
}

void thief(int capacity, vi& value, vi& weight)
{
  for (auto& i : dp) {
    for (auto& j : i) {
      j = pii(-1,-1);
    }
  }
  pii res = rec(capacity, 0, value, weight);
  cout << res.first << endl;
  cout << res.second << endl;
}

int main(int argc, char **argv)
{
  int casenr = 0;
  for (;;) {
    int W, N;
    cin >> W;
    if (!W)
      break;
    cin >> N;
    vi value(N), weight(N);
    rep (i, N) {
      char c;
      cin >> value[i] >> c >> weight[i];
    }
    cout << "Case " << ++casenr << ":" << endl;
    thief(W, value, weight);
  }
  return 0;
}

Measured memory_bytes: 9184
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

template <class T>
class cumulativeSum
{
private:
    int ny, nx;
    vector<vector<T> > sum;
public:
    cumulativeSum(){
    }
    cumulativeSum(const vector<vector<T> >& a)
    {
        ny = a.size();
        nx = a[0].size();
        sum.assign(ny+1, vector<T>(nx+1, 0));
        for(int i=0; i<ny; ++i){
            for(int j=0; j<nx; ++j){
                sum[i+1][j+1] = a[i][j] + sum[i][j+1] + sum[i+1][j] - sum[i][j];
            }
        }
    }
    T getSum(int y1, int x1, int y2, int x2)
    {
        y1 = max(y1, 0);
        x1 = max(x1, 0);
        y2 = min(y2, ny-1);
        x2 = min(x2, nx-1);
        if(y1 > y2 || x1 > x2)
            return 0;
        return sum[y2+1][x2+1] - sum[y1][x2+1] - sum[y2+1][x1] + sum[y1][x1];
    }
};

const int INF = INT_MAX / 2;

int h, w;
cumulativeSum<int> cs;
vector<vector<int> > memo;

int solve(int y, int x)
{
    if(y == h && x == w)
        return 0;
    if(memo[y][x] != -1)
        return memo[y][x];

    bool isFirst = ((y + x) % 2 == 0);
    int ans = (isFirst ? -INF : INF);
    if(y < h){
        int tmp = solve(y+1, x);
        tmp += cs.getSum(y, x, y, w-1);
        if(isFirst)
            ans = max(ans, tmp);
        else
            ans = min(ans, tmp);
    }
    if(x < w){
        int tmp = solve(y, x+1);
        tmp -= cs.getSum(y, x, h-1, x);
        if(isFirst)
            ans = max(ans, tmp);
        else
            ans = min(ans, tmp);
    }

    return memo[y][x] = ans;
}

int main()
{
    cin >> w >> h;
    vector<vector<int> > s(h, vector<int>(w));
    for(int i=0; i<h; ++i){
        for(int j=0; j<w; ++j){
            cin >> s[i][j];
        }
    }
    cs = cumulativeSum<int>(s);

    memo.assign(h+1, vector<int>(w+1, -1));
    cout << abs(solve(0, 0)) << endl;

    return 0;
}

Measured memory_bytes: 14732
#include<iostream>
#include<ios>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<vector>

#define ll long long

using namespace std;

int c[4][4];
int a[4], b[4];
bool judge;

int main()
{
    for (int i=1; i<=3; i++) {
        for (int j=1; j<=3; j++) {
            cin >> c[i][j];
        }
    }

    for (a[1] = 0; a[1] <= c[1][1]; a[1]++) {
        judge = true;

        for (int j=1; j<=3; j++) {
            b[j] = c[1][j] - a[1];
        }
        for (int i=2; i<=3; i++) {
            a[i] = c[i][1] - b[1];
        }

        for (int i=2; i<=3; i++) {
            for (int j=2; j<=3; j++) {
                if (c[i][j] != a[i] + b[j]) {
                    judge = false;
                }
            }
        }

        if (judge) {
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
#define fi first
#define se second
#define endl '\n'
#define y1 holyshit
#define all(x) x.begin(),x.end()
const int inf=0x3f3f3f3f;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int K; cin>>K;
	string S; cin>>S;
	if(S.size()<=K){
		cout<<S;
		return 0;
	}
	while(S.size()>K) S.pop_back();
	for(int i=0;i<3;i++) S.push_back('.');
	cout<<S;
	return 0;
}

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

const long long INF = 1e6+7;
const long long MOD = 1e9+7;

using namespace std;

int main(){
	
	int n;
	cin >> n;
	vector<long long> l(n);
	for(int i=0;i<n;i++){
		cin >> l[i];
	}
	sort(l.begin(),l.end());
	long long ans=0;
	for(int i=0;i<n-2;i++){
		for(int j=i+1;j<n-1;j++){
			for(int k=j+1;k<n;k++){
				if(l[k]<l[j]+l[i] && l[i]!=l[j] && l[j]!=l[k] && l[i]!=l[k]){
					ans++;
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3624
#include <cstdio>
#include <cstdlib>

using namespace std;

const int mod = 1000000007;

class inverse {
    public:
    inverse(int n, int mod);
    ~inverse();
    long long get_inv(int x);
    long long get_fact(int x);
    long long get_invfact(int x);
    long long get_comb(int x, int y);
    
    private:
    int mod;
    long long* inv;
    long long* fact;
    long long* invfact;
};

inverse::inverse(int n, int mod) : mod(mod) {
    inv = (long long *)malloc(sizeof(long long) * (n + 1));
    fact = (long long *)malloc(sizeof(long long) * (n + 1));
    invfact = (long long *)malloc(sizeof(long long) * (n + 1));
    inv[1] = 1;
    for (int i = 2; i <= n; i++) inv[i] = inv[mod % i] * (mod - mod / i) % mod;
    fact[0] = invfact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % mod;
    for (int i = 1; i <= n; i++) invfact[i] = invfact[i - 1] * inv[i] % mod;
}

inverse::~inverse() {
    free(inv);
    free(fact);
    free(invfact);
}

long long inverse::get_inv(int x) {
    return inv[x];
}

long long inverse::get_fact(int x) {
    return fact[x];
}

long long inverse::get_invfact(int x) {
    return invfact[x];
}

long long inverse::get_comb(int x, int y) {
    return fact[x] * invfact[y] % mod * invfact[x - y] % mod;
}

int main() {
    int h, w, k, i;
    long long ans = 0;
    
    scanf("%d %d %d", &h, &w, &k);
    
    inverse inv(h + w, mod);
    
    for (i = 1; i <= k; i++) {
        ans += inv.get_fact(h + w) * inv.get_invfact(h + w - k) % mod * h % mod * w % mod * inv.get_inv(h + w) % mod * inv.get_inv(h + w - 1) % mod * (i - 1) * 2 % mod * (k - i + 1) % mod;
        ans += inv.get_fact(h + w) * inv.get_invfact(h + w - k) % mod * h % mod * inv.get_inv(h + w) % mod * (k - i + 1) % mod;
        ans += inv.get_fact(h + w) * inv.get_invfact(h + w - k) % mod * w % mod * inv.get_inv(h + w) % mod * (k - i + 1) % mod;
    }
    
    ans += inv.get_fact(h + w) * inv.get_invfact(h + w - k) % mod * k % mod;
    
    printf("%lld\n", ans % mod);
    
    return 0;
}


Measured memory_bytes: 468992