akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=200005;
int n;
LL a[N];
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%lld",&a[i]),a[i]+=a[i-1];
	sort(a,a+n+1);
	LL ans=0;
	for (int i=0,j;i<=n;i=j+1){
		j=i;
		while (j<n&&a[j]==a[j+1])
			j++;
		ans=ans+1LL*(j-i+1)*(j-i)/2;
	}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 1792
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>

inline void read(int &T) {
	int x=0;bool f=0;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	T=f?-x:x;
}

int n,a,b,c;
char ans[100001];
std::string cmd[100001];

void dfs(int step,int a,int b,int c) {
	if(step>n) {
		puts("Yes");
		for(int i=1;i<=n;++i) {
			printf("%c\n",ans[i]);
		}
		exit(0);
	}
	if(cmd[step]=="AB") {
		if(a) {
			ans[step]='B';
			dfs(step+1,a-1,b+1,c);
		}
		if(b) {
			ans[step]='A';
			dfs(step+1,a+1,b-1,c);
		}
	}
	if(cmd[step]=="AC") {
		if(a) {
			ans[step]='C';
			dfs(step+1,a-1,b,c+1);
		}
		if(c) {
			ans[step]='A';
			dfs(step+1,a+1,b,c-1);
		}
	}
	if(cmd[step]=="BC") {
		if(b) {
			ans[step]='C';
			dfs(step+1,a,b-1,c+1);
		}
		if(c) {
			ans[step]='B';
			dfs(step+1,a,b+1,c-1);
		}
	}
}

int main() {
	read(n),read(a),read(b),read(c);
	for(int i=1;i<=n;++i) std::cin>>cmd[i];
	dfs(1,a,b,c);puts("No");
	return 0;
}

Measured memory_bytes: 14684
//#pragma once
#include <stdio.h>
#include <string>
#include <iostream>
#include <queue>
#include <algorithm>
#include <sstream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cctype>


using namespace std;
#define modd 1000000007


typedef pair<long long, long long> pl;


typedef string::const_iterator State;
class ParseError {};




#define ll long long




/*
class UnionFind {
public:
	vector <ll> par;
	vector <ll> siz;
	vector <ll> gr;

	// Constructor
	UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) ,gr(sz_){
		for (ll i = 0; i < sz_; ++i) par[i] = i;
	}
	void init(ll sz_) {
		par.resize(sz_);
		siz.assign(sz_, 1LL);  // resize だとなぜか初期化されなかった
		for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
	}

	// Member Function
	// Find
	ll root(ll x) { // 根の検索
		while (par[x] != x) {
			x = par[x] = par[par[x]]; // x の親の親を x の親とする
		}
		return x;
	}

	// Union(Unite, Merge)
	bool merge(ll x, ll y) {
		x = root(x);
		y = root(y);
		if (x == y) return false;

		// merge technique（データ構造をマージするテク．小を大にくっつける）
		if (siz[x] < siz[y]) swap(x, y);
		siz[x] += siz[y];
		par[y] = x;
		return true;
	}



	bool issame(ll x, ll y) { // 連結判定
		return root(x) == root(y);
	}

	ll size(ll x) { // 素集合のサイズ
		return siz[root(x)];
	}


};*/


long long N, M, K, a, b, c, d, e, H, W, L;
ll A[2][100005] = {};
ll B[2][100005] = {};
ll C[200005] = {};
bool f, ff;
string S;
set <long long>sll;
pl bufpl;
vector <long long>vl[3];
vector <pl>vpl;
vector <string> vs;
set<ll> llset;

/*struct ST
{
	long long Kati;
	int bangou;

	bool operator<(const ST& another) const
	{
		return Kati < another.Kati;//比較
	};

};



vector <ST> vst;
ST st[200005];
ST bufst;
bitset<5000> bits;*/


long long modinv(long long aa, long long mm) {
	long long bb = mm, uu = 1, vv = 0;
	while (bb) {
		long long tt = aa / bb;
		aa -= tt * bb; swap(aa, bb);
		uu -= tt * vv; swap(uu, vv);
	}
	uu %= mm;
	if (uu < 0) uu += mm;
	return uu;
}



ll minn, maxx;
double ansa;
bool fl[30] = {};

string ss, sss;

int main() {


	cin >> a>>b;

	c = abs(a - b);

	cout << c << endl;

	return 0;

}



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

using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

#define REP(i, l, n) for(int i=(l), i##_len=(n); i<i##_len; ++i)
#define ALL(x) (x).begin(),(x).end()
#define pb push_back

ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

const ll MAX = 1000000; //テーブルの数
const ll MOD = 1e9+7; //mod宣言

long long fac[MAX], finv[MAX], inv[MAX];
// finv ->階乗割り算
// fac ->階乗掛け算

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return (fac[n] * (finv[k] * finv[n - k] % MOD)) % MOD;
}

int main(){
    COMinit();
    int n, k; cin >> n >> k;
    if(n == 2){
        if(k == 0){
            cout << 1 << endl << 1 << " " << 2 << endl;
            return 0;
        }else{
            cout << -1 << endl;
            return 0;
        }
    }
    if(k > COM(n-1, 2)){
        cout << -1 << endl;
        return 0;
    }
    vector<Pii> graph;
    vector<Pii> edge;
    REP(i, 2, n+1){
        graph.pb({1, i});
    }
    int mid = COM(n-1, 2);
    vector<vector<int> > flag(n+1, vector<int>(n+1, 0)); 
    REP(i, 2, n){
        REP(l, i+1, n+1){
            if(flag[i][l] == 0 && flag[l][i] == 0){
                flag[i][l] = 1;
                flag[l][i] = 1;
                edge.pb({i, l});
            }
        }
    }
    int i = edge.size()-1;
    while(mid != k){
        graph.pb(edge[i]);
        i--;
        mid--;
    }
    cout << graph.size() << endl;
    REP(i, 0, graph.size()){
        cout << graph[i].first << " " << graph[i].second << endl;
    }
    return 0;
}

Measured memory_bytes: 23936
s = list(input())
t = list(input())
length = len(s)
count = 0
for i in range(length):
  newlst = []
  newlst.append(s[length-1])
  for j in range(length-1):
    newlst.append(s[j])
  s = newlst
  if s == t:
    print("Yes")
    count += 1
    exit()
if count == 0:
  print("No")
  

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

#ifdef LOCAL
#define debug(var) cerr << (#var) << " = " << (var) << endl;
#else
#define debug(var)
#endif

void init() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
}

const int N = 1e5+23;
int a[N];

void solve() {
  int n, x; scanf("%d%d", &n, &x);
  for (int i = 0; i < n; ++i) {
    scanf("%d", a+i);
    a[i] = a[i]-x;
  }
  int g = a[0];
  for (int i = 1; i < n; ++i) {
    g = __gcd(g, a[i]);
  }
  printf("%d", abs(g));
}

/*
33 105 57
48 24 24

 */

int main() {
  init();
  int t = 1; //scanf("%d", &t);
  while (t--) {
    solve();
  }
  return 0;
}


Measured memory_bytes: 4008
#include <stdio.h>

int main (){
	
	int h, w, n;
	scanf("%d %d %d", &h, &w, &n);
	
	int tot;
	
	if(h>=w) {
        if(n%h == 0) {
            tot = n/h;
        } else {
            tot = n/h+1;
        }
    } else {
        if(n%w == 0) {
            tot = n/w;
        } else {
            tot = n/w+1;
        }
    }
	printf("%d", tot);
	
	return 0;
}

Measured memory_bytes: 1712
using System;

namespace ITP1_1_D_Watch
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine( new DateTime( 0 ).Add( new TimeSpan( 0, 0, int.Parse( Console.ReadLine() ) ) ).ToString( "H:m:s" ) );
        }
    }
}

Measured memory_bytes: 5820
#include <stdio.h>
#include <math.h>



struct Circle{   // 円定義構造体
	float x,y;   // x,y:中心点座標
	float r;   // r:円の半径
};


int main(){
	struct Circle C1;
	struct Circle C2;
	int check;
	int d;
	
	scanf("%f %f %f", &C1.x, &C1.y, &C1.r);
	scanf("%f %f %f", &C2.x, &C2.y, &C2.r);
	



	// 円同士の当たり判定
	int r = C1.r + C2.r;   // ２円の半径の合計
	float r2 = C1.r - C2.r;
	int x = C1.x - C2.x;   // X座標の差
	int y = C1.y - C2.y;   // Y座標の差

 d = sqrt(x*x+y*y);

	if(d>r)check=4;
	else if (d==r)  check=3;
	else if(fabs(r2)<d && d<r)check=2;
	else if(d==fabs(r2)) check=1;
	else check=0;

		printf("%d\n",check);

			return 0;
}




Measured memory_bytes: 2100
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
using ld = long double;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,a,n) for(ll i=a;i<(ll)(n);++i)
#define repr(i,a,n) for(ll i=n-1;(ll)a<=i;--i)
#define ENDL '\n'
typedef pair<int,int> Pi;
typedef pair<ll,ll> PL;
constexpr ll mod = 998244353;
constexpr ll INF = 1000000099;
constexpr ll LINF = (ll)(1e18 +99);
const vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};
template<typename T,typename U> inline bool chmin(T& t, const U& u){if(t>u){t=u;return 1;}return 0;}
template<typename T,typename U> inline bool chmax(T& t, const U& u){if(t<u){t=u;return 1;}return 0;}
template<typename T> inline T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T,typename Y> inline T mpow(T a, Y n) {
  T res = 1;
  for(;n;n>>=1) {
    if (n & 1) res = res * a;
    a = a * a;
  }
  return res;
}

ll dp[3010][3010]={};
ll sum[3010][3010]={};


signed main(){
  cin.tie(0);ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(20);
  ll n,s,ans=0;cin>>n>>s;
  V<ll> v(n);
  rep(i,0,n)cin>>v[i];
  dp[0][0]=1;

  rep(i,1,n+1){
    rep(j,0,3010){
      dp[i][j]=dp[i-1][j];
      dp[i][j]%=mod;

      sum[i][j]+=sum[i-1][j];
      sum[i][j]%=mod;

      if(j-v[i-1]>=0){
        dp[i][j]+=dp[i-1][j-v[i-1]];
        dp[i][j]%=mod;

        sum[i][j]+=sum[i-1][j-v[i-1]];    
        if(j==v[i-1])sum[i][j]+=i;
        sum[i][j]%=mod;
      }
    }

    ans+=sum[i][s]%mod;
    //cerr<<ans<<ENDL;
    ans%=mod;
  }

  cout<<ans<<ENDL;
}
//! ( . _ . ) ! 
//CHECK overflow,vector_size,what to output?

Measured memory_bytes: 141568
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, [ $t:tt ]) => {{
        let len = read_value!($next, usize);
        (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    }};

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused)]
macro_rules! debug {
    ($($format:tt)*) => (write!(std::io::stderr(), $($format)*).unwrap());
}
#[allow(unused)]
macro_rules! debugln {
    ($($format:tt)*) => (writeln!(std::io::stderr(), $($format)*).unwrap());
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (let _ = write!(out,$($format)*););
    }
    input! {
        h: i64, w: i64,
    }
    if h == 1 || w == 1 {
        puts!("1\n");
    } else {
        puts!("{}\n", (h * w + 1) / 2);
    }
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


Measured memory_bytes: 8572
import sys
A, B, C = list(map(int, input().split()))
if A % 2 != 0 or B % 2 != 0 or B % 2 != 0:
    print('0')
    sys.exit()
if A == B == C:
    print('-1')
    sys.exit()
cnt = 0
while A % 2 == 0 and B % 2 == 0 and C % 2 == 0:
    _A = A
    _B = B
    _C = C
    A = _B // 2 + _C // 2
    B = _A // 2 + _C // 2
    C = _A // 2 + _B // 2
    cnt += 1
print(cnt)


Measured memory_bytes: 9004
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
using ll = long long;
int main(int argc, char const *argv[]) {
  ll n,m;
  cin>>n>>m;
  vector<pair<ll,ll>> stores(n);
  for(int i=0;i<n;i++){
    ll a,b;
    cin>>a>>b;
    stores[i]=make_pair(a,b);
  }
  sort(stores.begin(),stores.end());
  ll value=0;
  int i=0;
  while(1){
    if(m>stores[i].second){
      value+=stores[i].first*stores[i].second;
      m-=stores[i].second;
    }else{
      value+=stores[i].first*m;
      break;
    }
    i++;
  }
  cout<<value<<endl;
  return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include<sstream>
#include<string>
#include<vector>
#include <cmath>
#include <limits>
#include <queue>
#include<algorithm>
#include<cstring>
#include <cstdlib>
#include <cstdio>
#include <set>
#include <iomanip>
#include <map>
#include <stack>
#include <memory>
#include <numeric>
#include <type_traits>

using namespace std;

#define rep(i,n) for (int (i)=0;(i)<(n);i++)
typedef long long ll;
const int MAXV = 1e6+100;



int main(){
  int N; cin >> N;
  vector<int> A(N);
  rep(i,N) cin >> A[i];
  sort(A.begin(),A.end());
  bool ans[A.back()+1];
  rep(i,N) ans[A[i]] = true;
  //map<int,int> dob;
  int res = 0, before = 0;
  rep(i,N){
    int a = A[i], n = 2;
    if (!ans[a]) continue;
    if (A[i] == before) ans[A[i]] = false;
    while(a*n <= A.back()){
      ans[a*n] = false;
      ++n;
    }
    before = A[i];
  }
  rep(i,N){
    if(ans[A[i]]) res++;
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 5024
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<tuple>
#include<iomanip>
#include<map>
#define int long 
using namespace std;

signed main() {
	int H,W;
	cin >> H >> W;
	vector<vector<char>> vec(H + 2,vector<char>(W + 2));
	for(int i = 0;i < H;i++) {
		for(int j = 0;j < W;j++) {
			cin >> vec.at(i + 1).at(j + 1);
		}
	}
	bool A = true;
	for(int i = 0;i < H;i++) {
		for(int j = 0;j < W;j++) {
			if(vec.at(i + 1).at(j + 1) == '#') {
				if(vec.at(i).at(j + 1) != '#' && vec.at(i + 2).at(j + 1) != '#' && vec.at(i + 1).at(j + 2) != '#' && vec.at(i + 1).at(j) != '#') {
					A = false;
				}
			}
		}
	}
	if(A == true) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    int i;
    for(i = 1; i <= 3; i++){
        if(i != n && i != m)    break;
    }
    printf("%d\n", i);
    return 0;
}

Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	as := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&as[i])
	}

	m := make(map[int]int, n)
	for i := range as {
		m[as[i]]++
	}

	cost := 0
	for k, v := range m {
		if k == v {
			continue
		}

		if diff := v - k; diff > 0 {
			cost += diff
		} else {
			cost += v
		}
	}
	fmt.Println(cost)
}


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

int main(){
    int N,W;// N:items W:weight limit
    int item[1000][2]; // 0:cost 1:weight
    cin>>N>>W;

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

    int cost[N+1][W+1];

    for(int i=0; i<=N; i++)
        for(int j=0; j<=W; j++)
            cost[i][j] = 0;

    for(int i=1; i<=N; i++){
        for(int j=1; j<=W; j++){
            if(item[i-1][1] <= j){
                cost[i][j] = max(cost[i-1][j],item[i-1][0] + cost[i-1][j-item[i-1][1]]);
            }
            else
                cost[i][j] = cost[i-1][j];
        }
    }
    cout<<cost[N][W]<<endl;
}


Measured memory_bytes: 7040
import java.util.Scanner;
class Main {
 public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  while(true) {
   int H = sc.nextInt();
   int W = sc.nextInt();
   if( H == 0 && W == 0 ) break;
   for( int i = 0; i < H; i++ ) {
    for( int j = 0; j < W; j++ ) {
     System.out.printf("#");
    }
    System.out.println("");
   }
   System.out.println("");
  }
 }
} 


Measured memory_bytes: 57300
# -*- coding: utf-8 -*-
# モジュールのインポート
import numpy as np

# 標準入力の取得
N, M, X = list(map(int, input().split()))
C = []
A = []
for n in range(N):
    line = list(map(int, input().split()))
    C.append(line[0])
    A.append(line[1:])

C = np.array(C)
A = np.array(A)

# 求解処理
result = sum(C)
canAchieve = False
for i in range(2**N):
    cost = 0
    skill = np.zeros(M)
    for j in range(N):
        if ((i >> j) & 1):
            cost += C[j]
            skill += A[j]

    if min(skill) >= X:
        result = min(result, cost)
        canAchieve = True

if not canAchieve:
    result = -1

# 結果出力
print(result)


Measured memory_bytes: 27044
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

static const int mod = 998244353;

int main() {
  int n;
  scanf("%d", &n);
  vector<pair<int, int>> robots;
  for (int i = 0; i < n; i++) {
    int x, d;
    scanf("%d %d", &x, &d);
    robots.emplace_back(x, d);
  }
  
  sort(robots.begin(), robots.end());
  stack<pair<int, int>> s;
  vector<vector<int>> e(n);
  vector<int> topo;
  for (int i = n - 1; i >= 0; i--) {
    while (!s.empty()) {
      auto p = s.top();
      if (p.first < robots[i].first + robots[i].second) {
        e[i].emplace_back(p.second);
        topo.emplace_back(p.second);
        s.pop();
      }
      else
        break;
    }

    s.push({robots[i].first, i});
  }

  vector<int> roots;
  while (!s.empty()) {
    int i = s.top().second;
    topo.emplace_back(i);
    roots.emplace_back(i);
    s.pop();
  }
  
  vector<int> f(n);
  for (int i = 0; i < n; i++) {
    long long t = 1;
    for (int j = 0; j < e[topo[i]].size(); j++)
      t = t * f[e[topo[i]][j]] % mod;
    f[topo[i]] = (t + 1) % mod;
  }

  int ans = 1;
  for (int i = 0; i < roots.size(); i++)
    ans = 1LL * ans * f[roots[i]] % mod;
  printf("%d\n", ans);

  return 0;
}


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



int main(){
	int n,x=0;
	cin >> n;
	vector<int> a(n);
	rep(i,n){
		cin >> a[i];
		x = x^a[i];
	}
	vector<int> b(n);
	rep(i,n){
		b[i] = x ^ a[i];
		cout << b[i] << " ";
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 4848
#include <iostream>
#include <climits>

using namespace std;

int const NMAX = 100;
int const VALMAX = 1e5;
long long const INF = 1e11;

int n, weight, val;
long long w[1 + NMAX], v[1 + NMAX]; //the minimum weight through which the value is achievable

long long dp[1 + NMAX][1 + VALMAX];

int main() {
    cin >> n >> weight;
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }
    val = n * 1000;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= val; j++) {
            dp[i][j] = INF;
        }
    }
    dp[1][0] = 0;
    dp[1][v[1]] = w[1];
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= val; j++) {
            dp[i][j] = dp[i - 1][j];
        }
        for (int j = v[i]; j <= val; j++) {
            dp[i][j] = min(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
        }
    }
    int maxVal = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= val; j++) {
//          cout << "dp[" << i << "][" << j << "] = " << dp[i][j] << endl;
            if (dp[i][j] <= weight) {
                maxVal = max(j, maxVal);
            }
        }
    }
    cout << maxVal;
    return 0;
}


Measured memory_bytes: 78464
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

void dump(vector<int> v){
    vector<int>::iterator it = v.begin();
    while(it!=v.end()){
        if(it!=v.begin()) cout << " ";
        cout << *it ;
        it++;
    }
    cout << endl;
}

int main(){
    int n, q, num, order, t;
    vector< vector<int> > a, out;
    cin >> n >> q;
    for(int i=0;i<n;i++){
        vector<int> at;
        a.push_back(at);
    }
    for(int i=0;i<q;i++){
        cin >> order >> t;
        switch (order){
        case 0:
            cin >>num;
            a[t].push_back(num);
            break;
        case 1:
            dump(a[t]);
            break;
        case 2:
            a[t].clear();
            break;
        default:
            break;
        }
    }  
}


Measured memory_bytes: 6840
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class Program
{
	public static void Main()
	{
		var s = Console.ReadLine().ToCharArray();
		var C = false;
		foreach (var c in s)
		{
			if (c == 'C')
			{
				C = true;
			}
			if (C && c == 'F')
			{
				Console.WriteLine("Yes");
				return;
			}
		}
		Console.WriteLine("No");
	}
}

Measured memory_bytes: 2648
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#include <map>
typedef long long ll;
#define REP(i, n) for(ll i = 0; i < n; i++)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using Graph = vector<vector<int>>;


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;
}
ll modinv(ll a, ll m){
    ll b = m, u = 1, v = 0;
    while(b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if(u < 0) u += m;
    //cout << u << endl;
    return u;
}

ll paty_counter(ll level, ll x){
    ll size = pow(2, level+2) - 3;
    ll pmi = pow(2, level) - 1;
    if(x == 0){
        return 0;
    }else if(level == 0){    
        return 1;
    }else{
        if(x <= (size - 1)/2){
            return paty_counter(level-1, x-1);
        }else{
            return pmi + 1 + paty_counter(level-1, x - pow(2, level+1) + 3 - 2);
        }
    }

}
 
int main() {
    ll n;
    cin >> n;
    vector<ll> a(n);
    ll s = 0;
    ll ss = 0;
    REP(i, n){
        cin >> a[i];
        s += a[i]%MOD;
        s %= MOD;
        ss += a[i]*a[i] % MOD;
        ss %= MOD;
    }
    ll r = (s*s%MOD - ss%MOD)%MOD;
    if(r < 0){
        r += MOD;
    }
    //cout << r << endl;
    ll u = modinv(2, MOD);
    cout << r * u % MOD << endl;
}



Measured memory_bytes: 4900
import itertools
from collections import Counter
n=int(input())
S=[input()[0] for i in range(n)]
ls=["M","A","R","C","H"]
S=Counter([i for i in S if i in ls])
ans=0
for i,j,k in itertools.combinations(ls,3):
  ans+=S[i]*S[j]*S[k]
print(ans)

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

int main() {
  int h, n;
  cin >> h >> n;
  int sum_a = 0;
  rep(i,n) {
    int tmp = 0;
    cin >> tmp;
    sum_a += tmp;
  }
  if (sum_a >= h) {
    cout << "Yes" << endl;
  } else {
  	cout << "No" << endl;
  }
  return 0;
}


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

using namespace std;

int main(){
        int a, b;
        cin>>a>>b;
        if((a+b)%3==0||a%3==0||b%3==0)
                cout<<"Possible"<<endl;
        else{
                cout<<"Impossible"<<endl;
        }
        return 0;
}


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

int main() {
  int N;
  cin >> N;
  vector<int> d(N);
  for (int i=0; i<N; i++) cin >> d.at(i);
  int sum=0;
  for (int i=0; i<N; i++){
    for(int j=0; j<N; j++){
      if(i!=j) sum += d.at(i)*d.at(j);
    }
  }
  cout << sum/2 << endl;
}



Measured memory_bytes: 256
from collections import deque
def main():
    from sys import stdin
    readline = stdin.readline

    from builtins import max, min, range

    INF = 10 ** 6

    H, W = map(int, readline().split())
    C1, C2 = map(lambda x: int(x) - 1, readline().split())
    D1, D2 = map(lambda x: int(x) - 1, readline().split())
    S = [readline()[:-1] for _ in range(H)]



    t = [[INF]*W for _ in range (H)]


    for h in range (H):
        Sh = S[h]
        th = t[h]
        for w in range (W):
            if Sh[w] == '#':
                th[w] = -1


    q = deque([(C1,C2)])
    a = 0
    t[C1][C2] = a

    while q:
        warpq = []
        while q:
            h,w = q.popleft()
            warpq.append((h,w))
            if 0 < h and t[h-1][w] > a:
                t[h-1][w] = a
                q.append((h-1,w))
            if H-1 > h and t[h+1][w] > a:
                t[h+1][w] = a
                q.append((h+1,w))
            if 0 < w and t[h][w-1] > a:
                t[h][w-1] = a
                q.append((h,w-1))
            if w < W-1 and t[h][w+1] > a:
                t[h][w+1] = a
                q.append((h,w+1))

        if t[D1][D2]!= INF:
            break

        a+=1

        for h,w in warpq:
            for i in range (max(0,h-2),min(H,h+3)):
                ti = t[i]
                for j in range (max(0,w-2),min(W,w+3)):
                    if ti[j] >a:
                        ti[j] = a
                        q.append((i,j))


    if t[D1][D2] == INF:
        print(-1)
    else:
        print(t[D1][D2])

main()


Measured memory_bytes: 23456
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

//試してて御免

const int cm = 1 << 18;
char ci[cm];
char *cn = ci + cm;
inline char getcha() { 
	if (cn - ci == cm) { fread(ci, 1, cm, stdin); cn = ci; }
	char ret = *cn;
	cn++;
	return ret;
}
inline char getcha2() {
	char ret = *cn;
	cn++;
	return ret;
}

inline int getint() {
	if (cn - ci + 25 > cm) {
		char C = getcha();
		int A = C - '0';
		while (isdigit(C = getcha())) A = A * 10 + C - '0';
		return A;
	}
	else {
		char C = getcha2();
		int A = C - '0';
		while (isdigit(C = getcha2())) A = A * 10 + C - '0';
		return A;
	}
}

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


	int N, X;
	N = getint();
	X = getint();

	int A = 0;
	ll kotae = 0;
	rep(i, N) {
		int B = getint();
		if (A + B > X) {
			kotae += A + B - X;
			B = X - A;
		}
		A = B;
	}
	co(kotae);

	Would you please return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
#include<utility>

using namespace std;

#define int long long
#define endl "\n"

constexpr long long INF = (long long)1e18;
constexpr long long MOD = 1'000'000'007; 

struct fast_io {
	fast_io(){
		std::cin.tie(nullptr);
		std::ios::sync_with_stdio(false);
	};
} fio;

signed main(){
	cout<<fixed<<setprecision(10);
	int A, B;
	
	cin>>A>>B;
	
	cout<<A*B<<endl;
	
	return 0;
}

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

int main(){
    int n;
    cin >> n;
    int a = n / 100;
    if(n <= 100*a+10*a+a){
        cout << 100*a+10*a+a << endl;
    } else {
        a++;
        cout << 100*a+10*a+a << 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++)

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a,b,c; cin>>a>>b>>c;
  if(a+b==c||a==b+c||a+c==b) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <queue>
#include <map>
#include <fstream>
#include <array>
#include <utility>
#include <functional>
#include <stack>
#include <math.h>
#include <numeric>
#include <set>

using namespace std;
typedef long long Int;
#define REP(i , x) for(Int i = 0 ; i < x ; ++i)
typedef pair<int, int> P;


int main()
{
	int n; 
	while (cin >> n, n){
		P origin;
		--n;
		cin >> origin.first >> origin.second;

		vector<P> type;
		REP(i, n){
			int a, b;
			cin >> a >> b;
			
			P temp(a-origin.first,b-origin.second);

			type.push_back(temp);
		}

		cin >> n;
		set<P> judge;
		vector<P> point;
		REP(i, n){
			int a, b;
			cin >> a >> b;
			point.push_back(P(a, b));
			judge.insert(P(a, b));
		}

		REP(i, point.size()){
			bool f(true);
			REP(j, type.size()){
				P p(point[i].first + type[j].first, point[i].second + type[j].second);

				f &= judge.find(p) != judge.end();
			}
			if (f){
				cout << point[i].first - origin.first << " " << point[i].second - origin.second << endl;
				break;
			}
		}
	}

	return 0;
}

Measured memory_bytes: 1256
N, X, Y = list(map(int, input().split()))
res = [0] * N
for j in range(1, N + 1):
    for i in range(1, j):
        if i == X and Y == j:
            key = 1
        else:
            key = int(min(j - i, abs(X - i) + abs(Y - j) + 1))
        res[key] += 1

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

Measured memory_bytes: 3444
import java.util.*;
import java.util.stream.*;

public class Main {

    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {

            int N = sc.nextInt();
            long[] A = new long[N];
            for (int i = 0; i < N; i++) {
                A[i] = sc.nextLong();
            }

            int min = Arrays.stream(A).parallel().mapToInt(a -> {
                int ret = 0;
                for (int i = 1; i < 50; i++) {
                    if (((a >> i) << i) != a) {
                        ret = i - 1;
                        break;
                    }
                }
                return ret;
            }).min().getAsInt();

            System.out.println(min);

        }
    }

}

Measured memory_bytes: 29268
#include <cstdio>

int main () {
    int H, W;
    for (int i = 0;;i++) {
        scanf("%d %d", &H, &W);
        if (H == 0 && W == 0) break;
        for (int h = 0; h < H; h++) {
            for (int w = 0; w < W; w++) {
                if ( h % 2 == 0) {
                    if ( w % 2 == 0) {
                        printf("#");
                    } else {
                        printf(".");
                    }
                } else {
                    if ( w % 2 == 0) {
                        printf(".");
                    } else {
                        printf("#");
                    }

                }
            }
            printf("\n");
        }
        printf("\n");
    }
    return 0;
}

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

int main()
{
    string N;
    cin >> N;
    int n = stoi(N);
    int fx = 0;

    for (int i = 0; i < N.length(); ++i) fx += (int)(N[i]) - 48;
    if (n % fx == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
 
using namespace std;
 
typedef long long ll;
 
#define forn(i, n) for (int i = 0; i < (int)n; i++)
#define for1(i, n) for (int i = 1; i <= (int)n; i++)
#define forq(i, s, t) for (int i = s; i <= (int)t; i++)
#define ford(i, s, t) for (int i = s; i >= (int)t; i--)
#define all(v) v.begin(), v.end()
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
 
const double EPS = 1e-15;
const double PI = acos(-1.0);
const int MAXN = (int)1000 + 7;
const int INF = (int)1e9 + 7;
const int MOD = (int)1e9 + 7;
const ll P = 239017;
 
#define TASK "cave"
 
int solve();
 
int main()
{
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("test.txt", "w", stderr);
    double tstart = TIME;
#else
 //   freopen(TASK".in", "r", stdin), freopen(TASK".out", "w", stdout);
#endif
    solve();
#ifdef _DEBUG
    double tend = TIME;
    cerr << tend - tstart << " s.\n";
#endif
    return 0;
}

int cnt[(int)1e5 + 123];
 
int solve() {
 int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> cnt[i];

int ans = 0;
for (int i = 0; i < n; i++){
if (cnt[i] == i + 1 && cnt[i + 1] == i + 2) ans++, i++;
else if (cnt[i] == i + 1) ans++;
}
cout << ans;
return 0;
 }


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

int main(void) {
    int N;
    cin >> N;
    vector< int > A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    sort(A.begin(), A.end());
    bool flag = false;
    for (int i = 0; i < N - 1; i++) {
        if (A[i] == A[i + 1]) {
            flag = true;
            break;
        }
    }
    if (flag) {
        printf("NO\n");
    } else {
        printf("YES\n");
    }
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
 
double eps = 1e-8, PI = acos(-1);
 
double Sqrt(double x){
  return (x<0?0:sqrt(x));
}
 
bool eq(double a, double b){
  return (-eps<a-b&&a-b<eps);
}
 
struct Point{
  double x,y,z;
  Point (double a=0,double b=0,double c=0): x(a),y(b),z(c) {}
  Point operator + (const Point &p)const{
    return Point(x+p.x,y+p.y,z+p.z);
  }
  Point operator - (const Point &p)const{
    return Point(x-p.x,y-p.y,z-p.z);
  }
  Point operator * (const double &r)const{
    return Point(x*r,y*r,z*r);
  }
  Point operator / (const double &r)const{
    return Point(x/r,y/r,z/r);
  }
};
 
typedef Point Vector;
 
double dot(Point a,Point b){
  return a.x*b.x+a.y*b.y+a.z*b.z;
}
 
Point cross(Point a,Point b){
  double nx=a.y*b.z-b.y*a.z;
  double ny=a.z*b.x-b.z*a.x;
  double nz=a.x*b.y-b.x*a.y;
  return Point(nx,ny,nz);
}
 
double norm(Point a){
  return dot(a,a);
}
 
double abs(Point a){
  return sqrt( norm(a) );
}
 
struct Segment{
  Point p0,p1;
  Segment(Point a=Point(),Vector b=Vector()):p0(a),p1(b){}
};
 
struct Circle{
  Point p;
  double r;
  Circle(Point a,double b):p(a),r(b){}
};
 
vector<Point> getCrossPoint(Circle s,Segment t){
  vector<Point> res;
  Vector a=s.p-t.p0;
  Vector b=t.p1-t.p0;
  double base=dot(a,b)/abs(b);
  double hh=norm(cross(a,b))/norm(b);
  if(s.r*s.r+eps < hh )return res;
  double w=Sqrt( s.r*s.r - hh );
  
  if(-eps<base-w&&base-w<abs(b)+eps)
    res.push_back(t.p0+b/abs(b)*(base-w));
  
  if(-eps<base+w&&base+w<abs(b)+eps)
      res.push_back(t.p0+b/abs(b)*(base+w));
  
  return res;
}
 
int main(){
  int N,Q;
  Point A[50];
  double B[50];
  long long C[50];
  cin>>N>>Q;
  for(int i=0;i<N;i++){
    cin>>A[i].x>>A[i].y>>A[i].z;
    cin>>B[i]>>C[i];
  }
  for(int i=0;i<Q;i++){
    long long ans=0;
    Segment a;
    cin>>a.p0.x>>a.p0.y>>a.p0.z;
    cin>>a.p1.x>>a.p1.y>>a.p1.z;
    for(int j=0;j<N;j++){
      vector<Point> flg=getCrossPoint(Circle(A[j],B[j]),a);
      if(flg.size())ans+=C[j];
    }
    cout<<ans<<endl;
  }     
  return 0;
}

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

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

using namespace std;

ll cal(ll k){
    ll sum = 0;
    for (ll i = 1; i <= k; ++i)
    {
        sum += i;
    }
    if(k <= 0) return 0;
    else return sum;
}

int main() {

    string s; cin >> s;
    ll ans = 0;
    ll cur = 0;
    ll streak = 0;
    rep(i,s.length()){
        if(s[i] == '<'){
            if(streak != 0){
                if(streak +1 > cur){
                    ans += cal(streak);
                    ans -= cur;
                }else{
                    ans += cal(streak-1);
                }
                cur = 0;
            }
            cur ++;
            ans += cur;
            streak = 0;
        }else {
            streak ++;
        }
    }

    if(streak != 0){
        if(streak +1 >= cur){
            ans += cal(streak);
            ans -= cur;
        }else{
            ans += cal(streak-1);
        }
    }

    cout << ans;
    return 0;
}











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

#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n,s) for(int i=(s);i<(n);i++)
#define rrep(i,n) for(int i=(n-1);i>=0;i--)
#define rreps(i,n,s) for(int i=s;i>=n;i--)
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

using ll = long long;
using namespace std;
constexpr long long MAX = 5100000;
constexpr long long INF = 1LL << 60;
constexpr int MOD = 1000000007;

int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int a,b,c,k;
cin>>a>>b>>c>>k;
ll sum=0;
if(a>k){
    sum+=k;
}
else{
    sum+=a;
    k-=a;
}
if(b<k){
    sum-=k-b;
}
cout<<sum<<endl;
return 0;
}

Measured memory_bytes: 3620
#include <stdio.h>

int main(){
	int w, n, a, b, i, j, array[31], tmp;
	char c;
	for (i = 0;i < 31;i++) array[i] = i;
	
	scanf("%d%d", &w, &n);
	
	for (i = 0;i < n;i++){
		scanf("%d%c%d", &a, &c, &b);
		tmp = array[a];
		array[a] = array[b];
		array[b] = tmp;
	}
	
	for (i = 1;i <=w;i++) printf("%d\n", array[i]);
	return 0;
}

Measured memory_bytes: 596
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>

#define rep(i, n) for (int i = 0; i < n; ++i)
#define debug(s, param) std::cerr << s << param << std::endl;

using namespace std;
using ll = long long;

int main() {
  int n;  cin >> n;
  vector<double> a(n, 0), b(n, 0);
  rep(i, n) cin >> a[i] >> b[i];

  vector<int> indices(n, 0);
  rep(i, n) indices[i] = i;

  double total = 0;
  double patterns = 0;
  do {
    double dist = 0;
    rep (i, (int)indices.size() - 1) {
      dist += sqrt((a[indices[i]] - a[indices[i+1]]) * (a[indices[i]] - a[indices[i+1]]) + (b[indices[i]] - b[indices[i+1]]) * (b[indices[i]] - b[indices[i+1]]));
    }
    ++patterns;
    total += dist;
  } while (next_permutation(indices.begin(), indices.end()));
  stringstream ss;
  cout << fixed << setprecision(9) << total / patterns << endl;

  return 0;
}

Measured memory_bytes: 3804
#include<bits/stdc++.h>
#define sf1(n) scanf("%d",&n)
#define sf2(n,q) scanf("%d %d",&n,&q)
#define f first
#define ss second
#define pb push_back
#define lli long long
#define mem(ar,false) memset(ar,false,sizeof(ar))
#define mpr make_pair
#define endl "\n"
#define mod 1000000007
#define inf 9000000000000000000LL
using namespace std;

int ar[502];
lli dp[505][505];

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

    int n;
    cin >> n;

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

    for(int i=n; i>=1; i--)
    {
        for(int j=i; j<=n; j++)
        {
            if(j==i)
            {
                dp[i][j] = 0;
            }
            else
            {
                dp[i][j] = inf;
                lli sum = 0;
                for(int k=i; k<=j; k++)
                    sum+=ar[k];
                for(int k=i; k<=j-1; k++)
                {
                    dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+sum);
                }
            }
        }
    }
    cout << dp[1][n] <<endl;
    return 0;

}



Measured memory_bytes: 5212
N, M, X, Y = map(int, input().split())
lst1 = sorted(map(int, input().split()))
lst2 = sorted(map(int, input().split()))
Z = int(lst2[0])
if  X < Z <= Y and int(lst1[-1]) < Z:
    print('No War')
else:
    print('War')   

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define re reverse
using namespace std;
signed main(){
    string b,c,a,d;
    cin>>b>>c;
    int lcs[3005][3005]={};
    for(int j=1;j<=b.size();j++){
	for(int k=1;k<=c.size();k++){
	    if(b[j-1]==c[k-1]) lcs[j][k]=lcs[j-1][k-1]+1;
	    else lcs[j][k]=max(lcs[j-1][k],lcs[j][k-1]);
	}
    }
    int x=c.size(),y=b.size();
    while(true){
	if(x==0||y==0) break;
	if(lcs[y-1][x]==lcs[y][x-1]&&lcs[y-1][x-1]==lcs[y-1][x]&&lcs[y][x]>lcs[y][x-1]){
	    a+=c[x-1];
	    x--,y--;
	}
	else{
	    if(lcs[y-1][x]>lcs[y][x-1]) y--;
	    else x--;
	}
    }
    reverse(a.begin(),a.end());
    cout<<a<<"\n";
}


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

using namespace std;

int main() {
	int N,K;
	cin >> N >> K;
	
	int stones[N+10],min_jump[N+10];
	for (int i = 0; i < N; ++i) {
		cin >> stones[i];
		min_jump[i] = 1e9;
	}
	
	multiset<pair<int,int> > sliding;
	min_jump[0] = 0;
	
	for (int i = 1; i < N; ++i) {
		sliding.insert(make_pair(stones[i-1],i-1));
		if (sliding.size() > K) {
			sliding.erase(make_pair(stones[i-K-1],i-K-1));
		}
		
		auto a = sliding.lower_bound(make_pair(stones[i],i));
		auto b = sliding.upper_bound(make_pair(stones[i],i));
		
		a--;
		
		if (a == sliding.end()) {
			min_jump[i] = min_jump[b->second] + abs(b->first - stones[i]);
		} else if (b == sliding.end()) {
			min_jump[i] = min_jump[a->second] + abs(a->first - stones[i]);
		} else {
			min_jump[i] = min(min_jump[a->second] + abs(a->first - stones[i]),min_jump[b->second] + abs(b->first - stones[i]));
		}		
	}
	
	cout << min_jump[N-1];
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+6;

char n[N];
int f[N],g[N];

int main()
{
	int i;
	scanf("%s",n+1);
	f[0]=0;g[0]=1;
	for(i=1;n[i]!='\0';i++)
		f[i]=min(f[i-1]+n[i]-'0',g[i-1]+'9'+1-n[i]),
		g[i]=min(f[i-1]+n[i]-'0'+1,g[i-1]+'9'-n[i]);
	printf("%d",f[i-1]);
	return 0;
}

Measured memory_bytes: 9088
import Control.Applicative
import Control.Monad
import Control.Monad.ST
-- import qualified Data.ByteString as BS
import Data.Functor
import Data.Function
import Data.Monoid
import Data.Maybe
import Data.List
import qualified Data.Foldable as Foldable
import qualified Data.Set as Set
--import qualified Data.Sequence as Sequence
import Data.List.Split
import Data.Bits
import Data.Char
import Data.Ix
import Data.Ratio
import Data.Ord
import Data.Tuple
import Data.Array
--import Data.Array.Unboxed
--import Data.Array.IArray
import Data.Array.MArray
import Data.Array.IO
import Data.Array.ST
import Data.IORef
import Data.STRef
import GHC.ST
-- import System.IO.Unsafe
 
-- templete
readInt = read :: String -> Int
readInteger = read :: String -> Integer
readDouble = read :: String -> Double
getInt = readLn :: IO Int
getInts = map readInt . words <$> getLine
getInteger = readLn :: IO Integer
getIntegers = map readInteger . words <$> getLine
getDouble = readLn :: IO Double
getDoubles = map readDouble . words <$> getLine
sjoin :: (Show a) => [a] -> String
sjoin = unwords . map show
tjoin :: (Show a, Show b) => (a, b) -> String
tjoin (x, y) = show x ++ (' ' : show y)
cond :: a -> a -> Bool -> a
cond t f c = if c then t else f
apply2 :: (a -> a -> b) -> [a] -> b
apply2 f [x,y] = f x y
apply3 :: (a -> a -> a -> b) -> [a] -> b
apply3 f [x,y,z] = f x y z
apply4 :: (a -> a -> a -> a -> b) -> [a] -> b
apply4 f [x,y,z,w] = f x y z w
fnTuple :: (a -> b, a -> c) -> a -> (b, c)
fnTuple (f,g) a = (f a, g a)
replace :: (Eq a) => a -> a -> [a] -> [a]
replace x y = map (\z -> if z==x then y else z)
binMap :: (a -> a -> b) -> [a] -> [b]
binMap f (x:xs@(y:_)) = f x y : binMap f xs
binMap _ _ = []
splitRec :: Int -> [a] -> [[a]]
splitRec _ [] = []
splitRec n xs = let (y,ys) = splitAt n xs in y : splitRec n ys
infixl 7 `divCeil`
divCeil :: Integral a => a -> a -> a
x `divCeil` y = (x+y-1) `div` y
coverC :: Ord a => (a, a) -> a -> Bool
coverC (l,r) x = l<=x && x<=r
coverH :: Ord a => (a, a) -> a -> Bool
coverH (l,r) x = l<=x && x<r
ibsearch :: (Int -> Bool) -> (Int,Int) -> Int
ibsearch f (ok,ng) = if abs (ok-ng) <= 1 then ok else let mid = (ok + ng) `div` 2 in ibsearch f (if f mid then (mid,ng) else (ok,mid))
-- templete

myTurn (a,b) h [] = False
myTurn (a,b) h eh = let t = [enemyTurn (a-1,b) (delete a h) eh | a `elem` h] ++ [enemyTurn (a,b+1) (delete b h) eh | b `elem` h] in if null t then enemyTurn (a,b) h eh else or t

enemyTurn (a,b) [] eh = True
enemyTurn (a,b) h eh = let t = [myTurn (a-1,b) h (delete a eh) | a `elem` eh] ++ [myTurn (a,b+1) h (delete b eh) | b `elem` eh] in if null t then myTurn (a,b) h eh else and t


main = do
    n <- getInt
    replicateM_ n $ do
        h <- getInts
        let eh = [i | i <- [1..13], i /= 7, i `notElem` h]
        putStrLn $ cond "yes" "no" $ myTurn (6,8) h eh



Measured memory_bytes: 4128
def countup(nums):
  flag = [False for _ in range(len(nums))]
  
  nums[0] += 1
  
  for i in range(len(nums)-1):
    if nums[i] == 10 or nums[i] - nums[i+1] >= 2:
      flag[i] = True
      nums[i+1] += 1
  
  if nums[-1] == 10:
    nums[-1] = 0
    nums.append(1)
    
  for i in range(len(nums)-2, -1, -1):
    if flag[i]:
      if nums[i+1] == 0:
        nums[i] = 0
      else:
        nums[i] = nums[i+1] - 1
  return nums

N = int(input())

nums = [0]

for i in range(N):
  nums = countup(nums)
  
for i in range(len(nums)-1, -1, -1):
  print(nums[i], end='')
  
print('')

Measured memory_bytes: 3064
#include<cstdio>
#include<algorithm>
#define maxn 1005
using namespace std;
bool cmp(int x,int y)
{
	return x<y;
}
int main(void)
{
	int n,k;
	int a[maxn];
	while(~scanf("%d%d",&n,&k))
	{
		for(int i=0;i<n;++i)
			scanf("%d",&a[i]);
			sort(a,a+n,cmp);
		int sum=0;
		for(int i=0;i<k;++i)
		sum+=a[i];
		printf("%d\n",sum);
	}
	return 0;
}

Measured memory_bytes: 3212
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef long long ll;

#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=(b-1);i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;

#define INF 1000000007

int main() {
  ll x,y;
  cin>>x>>y;
  ll ans = 1;
  rep(i,0,1000){
    x*=2;
    if(x<=y){
      ans++;
    }
    else{
      break;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int N;
const int MAX_N = 101;
int A[MAX_N];

void insertionSort(int A[], int N) {
	for (int i = 1; i < N; i++) {

		//途中経過出力
		for (int k = 0; k < N - 1; k++) {
			cout << A[k] << " ";
		}
		cout << A[N - 1] << endl;

		int v = A[i];
		int j = i - 1;
		while (j >= 0 && A[j] > v) {
			A[j + 1] = A[j];
			j--;
			A[j + 1] = v;
		}
		
	}

	//答え
	for (int k = 0; k < N - 1; k++) {
		cout << A[k] << " ";
	}
	cout << A[N - 1] << endl;;
}

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

	return 0;
}


Measured memory_bytes: 3096
#include<iostream>
#include<climits>
#include<math.h>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<stdio.h>
#include <string>
#include <complex>
#include <functional>
#include <map>
#include <queue>
using namespace std;
using ll = long long;
//typedef pair<string,string> P;
//double dat[100][100];
//int dp[6][1010];//動的計画法
//int prime[100001];
//char str[1010][1010];
//typedef pair<ll,ll> A;
//vector<A> pc;
//int ABS(int a){return max(a,-a);}
int main() {
  int n,k;
  cin>>n>>k;
  int ans;
  ans=n-k+1;
  cout<<ans;
  return 0;
}

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

int main() {
  int N;
  cin >> N;
  map<string, long long int> anagramCounter;

  for(int i=0;i<N;i++) {
    string s;
    cin >> s;
    sort(s.begin(), s.end());
    anagramCounter[s]++;
  }
  long long int total = 0;
  for(auto i=anagramCounter.begin();i!=anagramCounter.end();i++) {
    total += i->second * (i->second-1) / 2; 
  }

  cout << total << endl;
  return 0;
}

Measured memory_bytes: 11136