akhauriyash/Code-Regression huggingface dataset:
#[allow(unused_macros)]
macro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut iter = $ s . split_whitespace ( ) ; let mut next = || { iter . next ( ) . unwrap ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; ( $ ( $ 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 ) * } } ; }
#[allow(unused_macros)]
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 ) * } } ; }
#[allow(unused_macros)]
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 : ty ) => { $ next ( ) . parse ::<$ t > ( ) . expect ( "Parse error" ) } ; }

fn main() {
    input! {
        n: usize,
        t: [u64; n]
    }

    let mut ret = t[0];
    for i in 1..n {
        ret = lcm(t[i], ret);
    }
    println!("{}", ret);
}

#[allow(dead_code)]
pub fn gcd(a: u64, b: u64) -> u64 {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}
#[allow(dead_code)]
pub fn lcm(a: u64, b: u64) -> u64 {
    a / gcd(a, b) * b
}
#[allow(dead_code)]
#[doc = " ax + by = gcd"]
#[doc = " (gcd, x, y)"]
pub fn extgcd(a: i64, b: i64) -> (i64, i64, i64) {
    if b == 0 {
        (a, 1, 0)
    } else {
        let (gcd, x, y) = extgcd(b, a % b);
        (gcd, y, x - (a / b) * y)
    }
}

Measured memory_bytes: 4352
N = int(input())
S = input()

s = [0 for _ in range(N+1)]
for i, x in enumerate(S):
    if x == "#":
        s[i+1] = s[i] + 1
    else:
        s[i+1] = s[i]
num = N
for i in range(N+1):
    w = s[i] - s[0]
    b = (N - i) - (s[N] - s[i])
    if w + b < num:
        num = w + b
print(num)

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

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

signed main() {
  bool ok = true;
  ll N;
  cin>>N;
  vector<ll> K(N+1);
  vector<ll> L(N+1), R(N+1);
  for(ll i=1; i<=N; i++)
    cin>>K[i];
  L[N] = R[N] = 2;
  for (ll i=N-1; i>=0; i--) {
    ll l = ((L[i+1] + K[i+1] - 1) / K[i+1]) * K[i+1];
    ll r = (R[i+1] / K[i+1]) * K[i+1];
    L[i] = l;
    R[i] = r + K[i+1]-1;
    if (L[i] > R[i])
      ok = false;
  }
  //for (ll i=0; i<=N; i++) {
  //  printf("i=%d: %d-%d\n", i, L[i], R[i]);
  //}

  if(ok)
    cout << L[0] << " " << R[0] << endl;
  else
    cout << -1 << endl;
  return 0;
}


Measured memory_bytes: 2560
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);

int A=sc.nextInt();
int B=sc.nextInt();
int C=sc.nextInt();

if( A + B + C == 17) {
System.out.println("YES");
} else {
System.out.println("NO");
}

}
}

Measured memory_bytes: 21332
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define pb push_back 
#define fr first
#define sc second
#define Rep(i,n) for(int i=0;i<(n);i++)
#define All(v) v.begin(),v.end()
#define Uniq(v) v.erase(unique(All(v)),v.end())
typedef pair<int, int> Pii; 
typedef pair<int, Pii> Pip;
typedef pair<string, int> Psi;
const int INF = (1<<30);
const int dx[]={1,0,-1,0}, dy[]={0,-1,0,1};

int main()
{
  string s; cin >> s;
  for(int i=0; i<12; i++) {
    cout << s[i];
    if( i == 3 ) cout << " ";
  } cout << endl;
}


Measured memory_bytes: 764
import std.stdio, std.algorithm, std.string, std.conv, std.array, std.range, std.math;
int read() { return readln.chomp.to!int; }
int[] reads() { return readln.split.to!(int[]); }

int s(string n) {
    int z;
    foreach (c; n) z += c - '0';
    return z;
}

void solve() {
    string n = readln.chomp;
    debug {
        writeln(n, s(n));
    }
    writeln(n.to!int % s(n) == 0 ? "Yes" : "No");
}

void main() {
    solve();
    readln;
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <deque>
#include <numeric>
#include <sstream>
#include <iomanip>
#define ALL(X) X.begin(), X.end()
using lint = long long;
template <typename T>
void print_container(std::vector<T> vec)
{
    for (auto iter = vec.begin(); iter != vec.end(); ++iter)
    {
        std::cout << *iter << " ";
    }
    std::cout << std::endl;
}

int main()
{
    lint n, k;
    scanf("%lld", &n);
    scanf("%lld", &k);

    std::set<lint> hate;

    for (int i = 0; i < k; ++i)
    {
        lint d;
        scanf("%lld", &d);
        hate.insert(d);
    }

    lint pay = n;

    while (1)
    {
        lint cur = pay;
        lint ok = 1;
        while (cur > 0)
        {
            if (hate.find(cur % 10) != hate.end())
            {
                pay++;
                ok = 0;
                break;
            }
            cur /= 10;
        }
        if (ok)
            break;
    }

    std::cout << pay << "\n";

    return 0;
}


Measured memory_bytes: 256
<?php

fscanf(STDIN,'%d',$length);
$line = trim(fgets(STDIN));
$arr = explode(' ',$line);

echo implode(' ',$arr), PHP_EOL;

for($i=1;$i<$length;$i++) {
    $compared=$arr[$i];
    $j=$i-1;
  while($j>=0&&$compared<$arr[$j]){
    $arr[$j+1]=$arr[$j];
    $arr[$j]=$compared;
    $j--;
  }

  echo implode(' ',$arr), PHP_EOL;
}


Measured memory_bytes: 9276
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
namespace AtCoder
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }

        static readonly long Mod = 1000000000 + 7;

        static void Main(string[] args)
        {
            var N = Sarray()[0];
            var wst = new Tuple<long,long,long,long>[N];
            for (var i = 0; i < N; ++i)
            {
                var t = Sarray();
                wst[i] = new Tuple<long,long,long, long>(t[0] + t[1], t[0], t[1], t[2]);
            }
            Array.Sort<Tuple<long, long, long, long>>(wst, (l, r) => (int)(l.Item1 - r.Item1));
            var len = wst[N - 1].Item2 + wst[N - 1].Item3;
            var dp = new long[N + 1, len + 1];
            for (var i = 0; i < N; ++i)
            {
                for (var j = 0; j <= len; ++j)
                    dp[i + 1, j] = dp[i, j];
                for (var j = 0; j <= wst[i].Item3; ++j)
                    dp[i + 1, j+wst[i].Item2] = Max(dp[i, j+wst[i].Item2], dp[i, j] + wst[i].Item4);
            }
            long max = 0;
            for (var i = 0; i <= len; ++i)
                max = Max(max, dp[N, i]);
            WriteLine(max);
        }
    }
}

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

int main() {
	int n;
	cin >> n;
	vector < vector <int> > a(2, vector <int> (n));
	for(int i = 0; i < 2; i++) {
		for(int j = 0; j < n; j++) {
			cin >> a[i][j];
		}
	}
	for(int j = 1; j < n; j++) {
		a[0][j] += a[0][j - 1];
	}
	a[1][0] += a[0][0];
	for(int j = 1; j < n; j++) {
		a[1][j] += max(a[0][j], a[1][j - 1]);
	}
	cout << a[1][n - 1];
	return 0;
}

Measured memory_bytes: 256
/*************************************************************************
    > File Name: e.cpp
    > Author: Amano Sei
    > Mail: amano_sei@outlook.com 
    > Created Time: 2020年01月03日 星期四 12时21分07秒
 ************************************************************************/

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int maxn = 100005;

int a[maxn];
long long s[maxn];

int main(){
    int n;
    long long m;
    scanf("%d%lld", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    sort(&a[1], &a[n+1]);
    for(int i = 1; i <= n; i++)
        s[i] = s[i-1]+a[i];
    for(int i = 0; i <= n; i++)
        s[i] = s[n]-s[i];

    register int cl = 2*a[1], cr = 2*a[n];
    register long long ans, cnt;
    while(cl <= cr){
        ans = cnt = 0;
        register int cm = (cl+cr)>>1;
        for(int i = 1; i <= n; i++){
            register int tl = 1, tr = n+1, cnum = cm-a[i];
            while(tl < tr){
                register int tm = (tl+tr)>>1;
                if(a[tm] < cnum)
                    tl = tm+1;
                else
                    tr = tm;
            }
            tl--;
            tr = n-tl;
            cnt += tr;
            ans += (long long)tr*a[i]+s[tl];
        }
        if(cnt > m)
            cl = cm+1;
        else if(cnt < m)
            cr = cm-1;
        else
            break;
    }
    if(cnt != m)
        ans += cr*(m-cnt);
    printf("%lld\n", ans);
}



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

#define pb push_back
#define ff first
#define ss second
#define N 1503
#define mod 1000000007
#define fo(n) for(int i=1;i<=n;i++)
typedef pair<int,int> pii;
typedef long long int ll;
typedef long int li;
int mod1 = 998244353;

int x,y,r,g,c;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin>>x>>y>>r>>g>>c;
    int red[r+3],green[g+2],col[c+2];
    fo(r) cin>>red[i]; fo(g) cin>>green[i];
    sort(red+1,red+r+1,greater<int>()); sort(green+1,green+g+1,greater<int>());
    vector<int>v;
    fo(x) v.pb(red[i]);  fo(y) v.pb(green[i]);
    sort(v.begin(),v.end());
    fo(c) cin>>col[i];
    sort(col+1,col+c+1,greater<int>());
    int i = 1,j = 1;
    while(i<=(x+y) && j<=c) {
        if(v[i-1] < col[j]) v[i-1] = col[j];
        else break;
        i++; j++;
    }
    ll ans = 0;
    fo(x+y) ans += v[i-1];
    cout<<ans;
    return 0;
}

Measured memory_bytes: 2292
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <string>

using namespace std;

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

	int ans = a + a*a + a*a*a;
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 3192
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sys/time.h>
#include <cmath>
#include <tuple>
#include <queue>
#include <bitset>

using namespace std;


int main() {
  struct timeval start,end;
  long long span;
  int a, b;

  gettimeofday(&start,NULL);

  std::cin >> a >> b;

  if (a >= 13) {
    std::cout << b << std::endl;
  } else if (a >= 6) {
    std::cout << b/2 << std::endl;
  } else {
    std::cout << 0 << std::endl;
  }

  gettimeofday(&end,NULL);
  span = (end.tv_sec -start.tv_sec)*1000000LL + (end.tv_usec - start.tv_usec);
  std::cerr << "--Total Time: " << span/1000 << "ms" << endl;
  return 0;
}


Measured memory_bytes: 888
#include<stdio.h>

int main(void){
	int N, K, d[100], a[100][100], i, j, ans[100] = {},sum=0;
	scanf("%d %d\n", &N, &K);
	for (i = 0; i < K; i++) {
		scanf("%d\n",&d[i]);
		for (j = 0; j < d[i]; j++) {
			scanf("%d", &a[i][j]);
			ans[a[i][j]-1] = 1;
		}
	}
	for (i = 0; i < N; i++) {
		if (ans[i] == 0) sum++;
	}
	printf("%d", sum);
	
	
	return 0;
}

Measured memory_bytes: 2192
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
ll GetDigit(ll num){ return log10(num)+1; } //numの桁数を求める

int main()
{
    int n;
    cin >> n;
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if(n%i == 0) ans += n/i - 1;
        else ans += n/i;
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
    int N, K;
    cin >> N >> K;
    long long h[N];
    for (int i = 0; i < N; i++) cin >> h[i];
    long long dp[N+100];
    for (int i = 0; i < N; i++) dp[i] = 1LL << 60;

    dp[0] = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 1; j <= K; j++) {
            dp[i+j] = min(dp[i+j], dp[i] + abs(h[i+j]- h[i]));
        }
    }

    cout << dp[N-1] << endl;
}

Measured memory_bytes: 1792
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = sr()
bl = False
for i in range(3):
    if N[i] == '7':
        bl = True
print('Yes' if bl else 'No')


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

using namespace std;

vector<int> F, T; // F = sidewards, T = upwards
string s;
int x, y;
set<int> dp[2];
int main(){
	//freopen("ftrobot.in", "r" ,stdin);
	cin >> s >> x >> y; 
	s += 'T';
	int cur = 0;
	bool dir = 0;
	bool firstturn = 1;
	for(auto i : s){
		if(i == 'T'){
			if(firstturn){
				dp[0].insert(cur); // forced to move this way
				firstturn = false;
			}
			else if(cur == 0){}
			else if(dir==0) F.push_back(cur);
			else T.push_back(cur);
			cur = 0;
			dir = 1-dir;
		}else cur++;
	}
//	printf("F: "); for(auto i : F) printf("%d ", i); printf("\n");
//	printf("T: "); for(auto i : T) printf("%d ", i); printf("\n");
	for(int i = 0; i<F.size(); i++){
		int ii = i%2;
		dp[1-ii].clear();
		for(auto j : dp[ii]){
			dp[1-ii].insert(j-F[i]);
			dp[1-ii].insert(j+F[i]);
		}
	}
	bool ans = true;
	if(dp[F.size()%2].find(x) == dp[F.size()%2].end()) ans = false;
	dp[0].clear();
	dp[0].insert(0);
	for(int i = 0; i<T.size(); i++){
		int ii = i%2;
		dp[1-ii].clear();
		for(auto j : dp[ii]){
			dp[1-ii].insert(j-T[i]);
			dp[1-ii].insert(j+T[i]);
		}
	}
	if(dp[T.size()%2].find(y) == dp[T.size()%2].end()) ans = false;
	cout << (ans ? "Yes" : "No");
}


Measured memory_bytes: 640
#include <iostream>
#include <list>
#include <random>

#define llong long long
#define rep(i,l,n) for(int (i)=(l);(i)<(n);(i++))

using namespace std;

int D;

llong change(int,int,int*,int*,int*,list<int>*);

int main(){
	cin >> D;
	int c[26],s[D*26],t[D];
	rep(i,0,26) cin >> c[i];
	rep(i,0,D) rep(j,0,26) cin >> s[i*26+j];
	rep(i,0,D) t[i] = i%26;
	
	list<int> day[26];
	rep(i,0,26) day[i].push_front(0);
	rep(i,0,D) day[t[i]].push_back(i+1);
	rep(i,0,26) day[i].push_back(D+1);
	
	random_device rd;
	mt19937 mt(rd());
	uniform_int_distribution<int> type(0,25);
	uniform_int_distribution<int> days(1,D);
	
	int M=10000;
	rep(i,0,M){
		int d,q;
		d = days(mt);
		q = type(mt);
		if( change(d,q,t,c,s,day) > 0 ){
			t[d-1] = q;
		}
	}
	
	rep(i,0,D) cout << t[i]+1 << endl;
	
	return 0;
}

// d���ڂɊJ�Â����R���e�X�g��q�ɕς���
llong change(int d,int q,int *t,int *c,int *s,std::list<int> *day){
	int p = t[d-1],delta=0;
	// �R���e�X�g p ���J�Â���Ȃ����Ƃɂ��e��
	for(list<int>::iterator itr=day[p].begin();itr!=day[p].end();itr++){
		if( *itr == d ){	// �K���ǂ����Ɋ܂܂��
			list<int>::iterator back=itr,next=itr; back--; next++;
			// �K��0���擪�Ɋ܂܂�Ă���̂�itr!=begin
			// �K��D+1���I�[�Ɋ܂܂�Ă���̂�next!=end
			delta -= c[p]*(d-*back)*(*next-d)+s[(d-1)*26+p];
			day[p].erase(itr);
			break;
		}
	}
	// �R���e�X�g q ���J�Â���邱�Ƃɂ��e��
	for(list<int>::iterator itr=day[q].begin();;itr++){
		if( *itr > d ){
			// �I�[��D+1�ŕK�������|���邱�Ƃ��ۏ؂����
			list<int>::iterator back=itr; back--;
			day[q].insert(itr,d);
			delta += c[q]*(d-*back)*(*itr-d)+s[(d-1)*26+q];
			break;
		}
	}
	return delta;
}


Measured memory_bytes: 3816
#include<bits/stdc++.h>
using namespace std;
#define ll long long
void solve(){
    ll n;
    cin>>n;
    vector<ll>h(n);
    for(int i=0;i<n;++i){
        cin>>h[i];
    }
    ll dp[n+1];
    dp[1]=0;
    dp[2]=abs(h[1]-h[0]);
    for(int i=3;i<=n;i++){
        dp[i]=min(abs(h[i-1]-h[i-3])+dp[i-2],abs(h[i-1]-h[i-2])+dp[i-1]);
    }
    cout<<dp[n];
}
int main(){
    int T=1;
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>

struct ARRAY {
  int index;
  int value;
};

bool asc( const ARRAY& left, const ARRAY& right ) {
    return left.value == right.value ? left.value < right.value : left.value < right.value;
}

int main() {
  int n;
  ARRAY A[200000+5];
  std::cin >> n;
  int answers[200000+5];

  for(int i=0; i<n; ++i) {
    std::cin >> A[i].value;
    A[i].index = i;
    answers[i] = 0;
  }
  int l = n-1;
  std::sort(A, A+n, asc);

  for(int i=0; i<n; ++i) {
    int index_val = A[i].value;
    if(index_val < A[(l+1)/2].value) {
      answers[A[i].index] = A[(l+1)/2].value;
    } else {
      answers[A[i].index] = A[(l+1)/2 - 1].value;
    }
  }

  for(int i=0; i<n; ++i) {
    std::cout << answers[i] << std::endl;
  }

}

Measured memory_bytes: 4480
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <limits.h>
#include <cmath>
#include <queue>
#include <map>
#include <iomanip>
#include <random>
#include <fstream>
#define rep(i, n) for (int i = 0; i < n; i++)
#define PI 3.14159265358979323846
#define MOD 1000000007
using namespace std;
using ll = long long;

const int MAX = 1000000;

ll fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
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;
}

ll gcd(ll a, ll b)
{
  ll r;
  while ((r = a % b))
  {
    a = b;
    b = r;
  }
  return b;
}

template <class T> struct cord{
  T x,y;
};

template <class T> double dist(cord<T> a, cord<T> b){
  T dx=a.x-b.x;
  T dy=a.y-b.y;
  return sqrt(dx*dx+dy*dy);
}

int main()
{

  //cout << fixed << setprecision(10);
  
  string s; cin >> s;
  sort(s.begin(),s.end());
  if (s=="abc"){cout << "Yes" << endl;}
  else {cout << "No" << endl;}

  return 0;
}


Measured memory_bytes: 256
#
# abc057 c
#
import sys
from io import StringIO
import unittest
import math


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """10000"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """1000003"""
        output = """7"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """9876543210"""
        output = """6"""
        self.assertIO(input, output)


def resolve():
    N = int(input())
    ans = float("inf")
    for a in range(1, int(math.sqrt(N))+1):
        if N % a == 0:
            b = N // a
            ans = min(ans, len(str(b)))
    print(ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()


Measured memory_bytes: 16244
#include <bits/stdc++.h>
using namespace std;
 
typedef pair<int, int> ii;
typedef pair<long long, long long> ll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<ii> vii;
typedef vector<ll> vll;
const long long INF = (long long)1e18;
 
int main() {
  int V, E, s, u, v, w, q;
  vector<vii> AdjList;
 
  scanf("%d", &V);
  E = V - 1;
 
  AdjList.assign(V, vii()); // assign blank vectors of pair<int, int>s to AdjList
  for (int i = 0; i < E; i++) {
    scanf("%d %d %d", &u, &v, &w);
    u--; v--;
    AdjList[u].push_back(ii(v, w));
    AdjList[v].push_back(ii(u, w));
  }
 
  scanf("%d %d", &q, &s);
  s--;
 
  // Dijkstra routine
  vl dist(V, INF); dist[s] = 0;                    // INF = 1B to avoid overflow
  priority_queue< ll, vector<ll>, greater<ll> > pq; pq.push(ll(0, s));
                             // ^to sort the pairs by increasing distance from s
  while (!pq.empty()) {                                             // main loop
    ll front = pq.top(); pq.pop();     // greedy: pick shortest unvisited vertex
    long long d = front.first, u = front.second;
    if (d > dist[u]) continue;   // this check is important, see the explanation
    for (int j = 0; j < (int)AdjList[u].size(); j++) {
      ll v = AdjList[u][j];                       // all outgoing edges from u
      if (dist[u] + v.second < dist[v.first]) {
        dist[v.first] = dist[u] + v.second;                 // relax operation
        pq.push(ll(dist[v.first], v.first));
  } } }  // note: this variant can cause duplicate items in the priority queue
 
    for(int qq = 0; qq < q; qq++) {
        scanf("%d %d", &u, &v);
        u--; v--;
        printf("%lld\n", dist[u] + dist[v]);
    }
 
  return 0;
}

Measured memory_bytes: 10096
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE UnboxedTuples #-}
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE ViewPatterns #-}
{-# LANGUAGE TupleSections #-}
{-# LANGUAGE MultiWayIf #-}

import Control.Monad
import Control.Monad.ST
import Control.Monad.State
import Control.Monad.Primitive
import Control.Applicative
import Control.Arrow
import Data.List
import Data.Array
import Data.Array.IO
import Data.Array.ST
import Data.IORef
import Data.STRef
import Data.Maybe
import Data.Bits
import Data.Ord
import Data.Ratio
import Data.Int
import Data.Char
import qualified Data.ByteString.Char8 as BS
import qualified Data.Set as Set
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as VM
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import Data.Tuple
import Data.Function
import Text.Printf
import Debug.Trace
import Numeric

modifyArray arr i f = readArray arr i >>= \x -> writeArray arr i (f x)

listToTuple2 [a,b] = (a,b)
listToTuple3 [a,b,c] = (a,b,c)
listToTuple4 [a,b,c,d] = (a,b,c,d)
listToTuple5 [a,b,c,d,e] = (a,b,c,d,e)

readIntBS = fst . fromJust . BS.readInt

for = flip map

infixr 1 ?
(?) :: Bool -> (a,a) -> a
(?) b t = (if b then fst else snd) t

main :: IO ()
main = do
  k <- readLn :: IO Int

  print $ (k`div`2) * (k`div`2 + k`mod`2)
  
  return ()
  
  


Measured memory_bytes: 508
/* ＵＴＦ－８ */
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <array>
#include <queue>
#include <stack>
#include <algorithm>
#include <tuple>
#include <numeric>
#include <type_traits>
#include <limits>

#include <stdio.h>
#include <unistd.h>
#include <fcntl.h>
#include <string.h>

#define USE_COLORED 1

#ifdef USE_COLORED
static const char stdout_pre[]  = "\033[1m"; // bold black
static const char stderr_pre[]  = "\033[31;1m"; // bold red
static const char stdxxx_post[] = "\033[m";

// 当然ながら GCC(g++)/libstdc++ 依存
#include <ext/stdio_filebuf.h>
using stdio_filebuf = __gnu_cxx::stdio_filebuf<char>;
class colored_stdio_filebuf : public stdio_filebuf {
private:
	const char* const pre_;
	const char* const post_;

public:
	colored_stdio_filebuf(FILE* fp, const char* pre, const char* post) : stdio_filebuf(fp, std::ios_base::out), pre_(pre), post_(post)
	{
	}

protected:
	std::streamsize xsputn(const char* s, std::streamsize count) override
	{
		stdio_filebuf::xsputn(pre_, strlen(pre_));
		auto ret = stdio_filebuf::xsputn(s, count);
		stdio_filebuf::xsputn(post_, strlen(post_));
		return ret;
	}
};
#endif

int main()
{
#ifdef USE_COLORED
	if (getenv("DEBUG")) {
		std::cout.rdbuf(new colored_stdio_filebuf(stdout, stdout_pre, stdxxx_post));
		std::cerr.rdbuf(new colored_stdio_filebuf(stderr, stderr_pre, stdxxx_post));
	} else
#endif
	{
		int fd = open("/dev/null", O_WRONLY);
		dup2(fd, 2);
		close(fd);
	}
	
	int N;
	std::vector<std::string> S;
	std::cin >> N;
	S.resize(N);
	for (auto& s : S)
		std::cin >> s;
	
	if (std::find(S.begin(), S.end(), std::string("Y")) != S.end()) {
		std::cout << "Four\n";
	} else {
		std::cout << "Three\n";
	}
}


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

using namespace std;
int n;
int a[2160];
int dp[2][2160];

int main(){
	cin >> n >> a[0] >> a[1];
	for(int i = 2;i < n+2;i++)cin >> a[i];

	for(int i = n;i >= 0;i--){
		//a's turn
		dp[1][i] = abs(a[i] - a[n+1]);
		for(int j = i+1;j <= n;j++){
			dp[1][i] = max(dp[1][i], dp[0][j]);
		}

		//b's turn
		dp[0][i] = abs(a[i] - a[n+1]);
		for(int j = i+1;j <= n;j++){
			dp[0][i] = min(dp[0][i], dp[1][j]);
		}
	}

	cout << dp[1][1] << endl;
	return 0;
	
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#define ll long long
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
ll read()
{
	ll tmp=0; char f=1,c=getchar();
	while(c<'0'||'9'<c){if(c=='-')f=-1; c=getchar();}
	while('0'<=c&&c<='9'){tmp=tmp*10+c-'0'; c=getchar();}
	return tmp*f;
}
using namespace std;
ll c[510],f[510],s[510];
ll n;
int main()
{
	int i,j;
	n=read();
	for(i=1;i<n;i++)
		c[i]=read(),s[i]=read(),f[i]=read();
	for(i=1;i<n;i++){
		ll tot=0;
		for(j=i;j<n;j++){
			tot=max(tot,max(f[j],s[j]));
			int tmp=tot/f[j];
			if(tot%f[j]!=0)tmp++;
			tot=tmp*f[j]+c[j];
			//printf("*** %lld\n",tot);
		}
		printf("%lld\n",tot);
	}
	printf("0\n");
	return 0;
}

Measured memory_bytes: 128
n = int(input())
l = list(map(int, input().split()))
sl = []

ma, mi = max(l), min(l)
if ma == mi:
  sl.append(0)

for x in range(mi, ma):
  s = 0
  for i in l:
    s += (i - x)**2 
  sl.append(s)

print(min(sl))

Measured memory_bytes: 9184
using System;
using System.Collections.Generic;
using System.Linq;

namespace CSharpSample01
{

    class Program
    {
        static int n;  //目的の値
        static int num;  //組み合わせる数
        static int count;

        static void SumInteger(int current, int i, int s)
        {
            int c = current + 1;  //現在の個数
            int sum = s;  //今の合計

            for (int j = i + 1; j <= 9; j++)
            {
                sum += j;

                if (c < num && sum >= n)
                {
                    return;
                }

                if (c == num)
                {
                    if (sum == n)
                    {
                        count++;
                        return;
                    }
                    else if (sum > n)
                    {
                        return;
                    }
                    else
                    {
                        sum -= j;
                        continue;
                    }
                }

                SumInteger(c, j, sum);

                sum -= j;
            }


        }


        static void Main(string[] args)
        {
            while (true)
            {
                string[] input = Console.ReadLine().Split(' ');

                num = int.Parse(input[0]);
                n = int.Parse(input[1]);
                count = 0;

                if (n == 0 && num == 0)
                {
                    break;
                }
                else
                {
                    SumInteger(0, -1, 0);
                }

                Console.WriteLine(count);
            }



        }
    }
}



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

/*第二引数で第一引数を割ったときの切り上げの計算*/
long long int maxtime(long long int x, long long int y) {
	return(x + y - 1) / y;

}
/*最大公約数*/
long long int lcm(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;

	if (number2 > number1) {
		m = number2;
		n = number1;
	}
	long long int s = -1;
	while (s != 0) {
		s = m % n;
		m = n;
		n = s;
	}
	return m;
}
/*最大公倍数*/
long long int gcd(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;
	return m / lcm(m, n) * n;
}
int main() {
	string s;
	long long int K;
	cin >> s;
	cin >> K;
	char b;
	long long int a = 0;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] != '1') {
			a = i;
			b = s[i];
			break;
		}
		if (i == s.size() - 1) {
			cout << 1;
			return 0;
		}
	}
	if (K - 1 < a) {
		cout << 1;
	}
	else {
		cout << b;
	}
	
}

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

int main(){
    string s,t;cin >> s >> t;
    rep(i,s.size()){
        string tmp;
        tmp=s[s.size()-1];
        string tmp2;tmp2.assign(s,0,s.size()-1);
        s=tmp+tmp2;
        //cout << s << endl;
        if(s==t){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	scn := newScanner()
	N := scn.nextInt()
	K := scn.nextInt()
	A := make([]int, N)
	maxA := 0
	for i := 0; i < N; i++ {
		A[i] = scn.nextInt()
		maxA = max(maxA, A[i])
	}
	g := A[0]
	for i := 0; i < N; i++ {
		g = gcd(g, A[i])
	}
	if K%g == 0 && maxA >= K {
		fmt.Println("POSSIBLE")
	} else {
		fmt.Println("IMPOSSIBLE")
	}
}

func max(a ...int) int {
	r := a[0]
	for i := 0; i < len(a); i++ {
		if r < a[i] {
			r = a[i]
		}
	}
	return r
}

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

type scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func newScanner() *scanner {
	rdr := bufio.NewReaderSize(os.Stdin, 10000)
	return &scanner{r: rdr}
}
func (s *scanner) next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}
func (s *scanner) nextLine() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)
	return string(s.buf[start:])
}
func (s *scanner) nextInt() int {
	v, _ := strconv.Atoi(s.next())
	return v
}
func (s *scanner) nextInt64() int64 {
	v, _ := strconv.ParseInt(s.next(), 10, 64)
	return v
}
func (s *scanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}
func (s *scanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}


Measured memory_bytes: 6528
#include <stdio.h>
#include <string.h>
#define NMAX 100000

int ufpar[NMAX], ufw[NMAX];

int UF_find(int);
int UF_weight(int);
int UF_union(int, int, int);
int UF_diff(int*, int, int);
int main(void)
{
  int i, n, m, l, r, d;
  scanf("%d %d", &n, &m);
  memset(ufpar, -1, sizeof(ufpar));
  for (i = 0; i < m; i++) {
    scanf("%d %d %d", &l, &r, &d);
    if (!UF_union(l - 1, r - 1, d)) {
      if (ufw[l-1] != ufw[r-1] + d) {
        printf("No\n");
        return 0;
      }
    }
  }
  printf("Yes\n");
}

int UF_find(int a)
{
  int p;
  if (ufpar[a] < 0) return a;
  p = UF_find(ufpar[a]);
  ufw[a] += ufw[ufpar[a]];
  return ufpar[a] = p;
}

int UF_weight(int a)
{
  UF_find(a);
  return ufw[a];
}

int UF_union(int x, int y, int w)
{
  w -= UF_weight(x);
  w += UF_weight(y);
  x = UF_find(x);
  y = UF_find(y);
  if (x == y) return 0;
  if (ufpar[x] > ufpar[y]) {
    ufpar[y] += ufpar[x];
    ufpar[x] = y;
    ufw[x] = w;
  } else {
    ufpar[x] += ufpar[y];
    ufpar[y] = x;
    ufw[y] = -w;
  }
  return 1;
}

int UF_diff(int *ans, int x, int y)
{
  if (UF_find(x) != UF_find(y)) return 0;
  else {
    *ans = ufw[x] - ufw[y];
    return 1;
  }
}

Measured memory_bytes: 896
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x)          (x).begin(), (x).end()
#define rep(i, n)       for (i64 i = 0, i##_limit = (n); i < i##_limit; ++i)
#define reps(i, s, t)   for (i64 i = (s), i##_limit = (t); i <= i##_limit; ++i)
#define repr(i, s, t)   for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#ifndef DBG
#define trace(...)
#endif
using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T, class U> inline bool chmax(T &a, const U &b) { return b > a && (a = b, true); }
template <class T, class U> inline bool chmin(T &a, const U &b) { return b < a && (a = b, true); }
constexpr int INF  = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

template <class T>
inline vector<T> make_v(const T &initValue, size_t sz) {
    return vector<T>(sz, initValue);
}

template <class T, class... Args>
inline auto make_v(const T &initValue, size_t sz, Args... args) {
    return vector<decltype(make_v<T>(initValue, args...))>(sz, make_v<T>(initValue, args...));
}

inline void read() {}

template <class Head, class... Tail>
inline void read(Head &head, Tail&... tail) { cin >> head; read(tail...); }

inline void print() { cout << "\n"; }

template <class Head, class... Tail>
inline void print(Head &&head, Tail&&... tail) {
    cout << head;
    if (sizeof...(tail)) cout << ' ';
    print(forward<Tail>(tail)...);
}

template <class T>
inline ostream& operator<< (ostream &out, const vector<T> &vec) {
    static constexpr const char *delim[] = { " ", "" };
    for (const auto &e : vec) out << e << delim[&e == &vec.back()];
    return out;
}
// }}} End Header

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

    int H, W;
    read(H, W);

    string mat[105];
    rep(i, H) {
        read(mat[i]);
    }

    bool row[105] {};
    bool col[105] {};
    rep(i, H) {
        if (count(all(mat[i]), '.') == W) row[i] = true;
    }
    rep(j, W) {
        bool x = true;
        rep(i, H) x &= mat[i][j] == '.';
        col[j] = x;
    }

    rep(i, H) {
        rep(j, W) {
            if (!row[i] && !col[j]) cout << mat[i][j];
        }
        if (!row[i]) cout << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define For(i , j , k) for (int i = (j) , _##end_ = (k) ; i <= _##end_ ; ++ i)
#define Fordown(i , j , k) for (int i = (j) , _##end_ = (k) ; i >= _##end_ ; -- i)
#define Set(a , b) memset(a , b , sizeof(a))
#define pb push_back
#ifdef hany01
#define debug(...) fprintf(stderr , __VA_ARGS__)
#else
#define debug(...)
#endif 
using namespace std;

inline void file()
{
	freopen("a.in" , "r" , stdin);
    freopen("a.out" , "w" , stdout);
}

char c_;
int _ , __;
inline int read()
{
    for (_ = 0 , __ = 1 , c_ = getchar() ; !isdigit(c_) ; c_ = getchar())
            if (c_ == '-')
                __ = -1;
    for ( ; isdigit(c_) ; c_ = getchar())
        _ = (_ << 1) + (_ << 3) + (c_ ^ 48);
    return _ * __;
}

const int maxn = 100015;
int n , a[maxn] , Max , cnt[maxn] , k;

int main()
{
#ifdef hany01
	file();
#endif
    n = read();
    For(i , 1 , n)
    {
        a[i] = read();
        ++ cnt[a[i]];
        ++ cnt[a[i] + 1];
        ++ cnt[a[i] + 2];
    }
    Max = 0;
    For(i , 0 , maxn - 5)
        if (Max < cnt[i])
            Max = cnt[i];
    printf("%d\n" , Max);
    return 0;
}

Measured memory_bytes: 1024
#include <vector> 
#include <list> 
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x * x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << '=' << (x) << endl;
#define debug(x) cerr << #x << '=' << (x) << '('<<'L' << __LINE__ << ')' << ' ' << __FILE__ << endl;

const LL mod = (LL)1e9 + 7;


#define Yes_ cout<<"Yes"<<endl; return 0;
#define No_ cout<<"No"<<endl; return 0;


#define YES_ cout<<"YES"<<endl; return 0;
#define NO_ cout<<"NO"<<endl; return 0;



int main() {
		
	LL A, B,K;
	cin >> A >> B >> K;
	vector<LL> ans;
	REP(i, K) {
		if(A+i<=B) ans.push_back(A + i);
		if(B-i>=A)ans.push_back(B - i);
	}
	sort(ALL(ans));
	int last = 0;
	REP(i, SZ(ans)) {
		if (ans[i] != last) {
			cout << ans[i] << endl;
			last = ans[i];
		}
	}




}

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

#define FASTIO  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ll long long int
#define ld long double
#define vll vector<ll>
#define it(r,v) for(auto r=v.begin();r!=v.end();r++)
#define l(i,a,b) for(int i=a;i<b;i++)
#define L(i,a,b) for(int i=a;i<=b;i++)
#define r(i,a,b) for(int i=a;i>=b;i--)
#define R(i,a,b) for(int i=a;i>b;i--)
#define scanl(a) scanf("%lld",&a)
#define scani(a) scanf("%d",&a)
#define scanll(a,b) scanf("%lld %lld",&a,&b)
#define scanil(a,b) scanf("%d %lld",&a,&b)
#define pr(a) cout<<a<<" "<<endl;
#define pr2(a,b) cout<<a<<" "<<b<<"\n"
#define pr3(a,b,c) cout<<a<<" a "<<b<<" b "<<c<<"\n"
#define input(a,n) l(i,0,n) cin>>a[i];

long long int m = 998244353;

//long long int mod = 1000000000;
//ll mod=998244353;
long long  int modularExponentiation(long long int x,long long int n)
{   x = abs(x);
    if(n==0)
        return 1;
    else if(n%2 == 0)        //n is even
        return  modularExponentiation((x*x),n/2)%m;
    else                             //n is odd
        return (x*(modularExponentiation((x*x)%m,(n-1)/2)))%m;
}

long long int GCD(long long int a,long long  int b)
{
    if (a == 0)
        return b;
    return GCD(b % a, a);
}

/*
int n=10;
struct node1 {
    long long int sum,prefix,suffix;
    sum=prefix=suffix=0;
};
struct node1 tree[2*n+2];

void join(int node){
    int l=2*node,r=l+1;
    tree[node].sum = tree[l].sum+tree[r].sum;
    tree[node].prefix = max(tree[l].prefix,tree[l].sum+tree[r].prefix);
    tree[node].suffix = max(tree[r].suffix,tree[l].suffix+tree[r].sum);
}

void build(int node , int l ,int r){
    if(l==r){
        tree[node].sum = a[l];
        tree[node].prefix = max(0,a[l]);
        tree[node].suffix = max(0,a[l]);
    } else {
        int mid = (l+r)/2;
        auto first,second;
        build(2*node,l,mid);
        build(2*node+1,mid+1,r);
        join(node,2*node,2*node+1);
    }
}

void update(int node,int l,int r,int p){
    if(l>r){
        return ;
    } else if(l==p && r==p){
        tree[node].sum=a[p];
        tree[node].prefix=max(0,a[p]);
        tree[node].suffix = max(0,a[p]);
    } else {
        int mid = (l+r)/2;
        update(2*node,l,mid,p);
        update(2*node+1,mid+1,r,p);
        join(node);
    }
}

node1 query(int node,int l,int r, int start,int last){
    if(start<=l && last>=r){
        return tree[node];
    } else if(l>r){
        return null;
    }
    int mid = (l+r)/2;
    auto first,second;
    first= query(2*node,l,mid,start,last);
    second = query(2*node+1,mid+1,r,start,last);
    join
}
*/



int main(){
    int n,k;
    cin>>n>>k;
    int a[n+1];
    a[0]=0;
    l(i,1,n+1)  cin>>a[i];
    long long int dp[n+1];
    l(i,0,n+1){
        dp[i]=1e18;
    }
    a[0]=a[1];
    dp[0]=0,dp[1]=0;
    l(i,2,n+1){
        l(j,1,k+1){
            if(i-j>=0){
                dp[i]=min(dp[i],dp[i-j]+abs(a[i]-a[i-j]));
            }
        }

    }
    cout<<dp[n]<<endl;
}




Measured memory_bytes: 4704
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=998244353,MAX=100005,INF=1<<28;

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    while(1){
        int N;cin>>N;
        if(N==0) break;
        map<string,int> MA;
        
        for(int i=0;i<N;i++){
            string S;cin>>S;
            MA[S]++;
        }
        
        int M;cin>>M;
        int cnt=1;
        
        for(int i=0;i<M;i++){
            string S;cin>>S;
            if(MA[S]==0){
                cout<<"Unknown "<<S<<endl;
            }else if(cnt%2==0){
                cout<<"Closed by "<<S<<endl;
                cnt++;
            }else{
                cout<<"Opened by "<<S<<endl;
                cnt++;
            }
        }
        
        break;
    }
}



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

int n, a, b, c;
vector<int> L(9);
int inf = 10000000;
int dfs(int x, int y, int z, int cnt){
    if (cnt == n){
        if (min({x, y, z}) > 0) return abs(x-a) + abs(y-b) + abs(z-c) - 30;
        return inf;
    }
    int ret1 = dfs(x + L[cnt], y, z, cnt + 1) + 10 ;
    int ret2 = dfs(x, y+ L[cnt], z, cnt + 1) + 10;
    int ret3 = dfs(x, y, z+ L[cnt], cnt + 1) + 10;
    int ret4 = dfs(x, y, z, cnt + 1);

    return min({ret1, ret2, ret3, ret4});
}

int main() {
    cin >> n >> a >> b >> c;
    for (int i = 0; i < n; i++) cin >> L[i];
    cout << dfs(0, 0, 0, 0) << endl;
}



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

int a[100001];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	sort(a,a+n,greater<int>());
	int col=0;
	while(col+1<n&&a[col+1]>col+1)
		col++;
	int u=0,r=0;
	u=a[col]-col;
	while(col+r<n&&a[col+r]>col)
		r++;
	if(!(u&1)||!(r&1))
		cout<<"First"<<endl;
	else
		cout<<"Second"<<endl;

}


Measured memory_bytes: 640
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<long long> vll;
typedef pair<int,int> pint;
typedef pair<long long, long long> pll;

#define MP make_pair
#define PB push_back
#define ALL(s) (s).begin(),(s).end()
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P) 
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P) 
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P) 
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P) 
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s; }

int a, b;

int main() {
	while (cin >> a >> b) {   
		if (a == 0) break;
		int rem = b-a;
		vint res(3);
		res[2] = rem / 1000;
		rem %= 1000;
		res[1] = rem / 500;
		rem %= 500;
		res[0] = rem / 100;
		cout << res[0] << " " << res[1] << " " << res[2] << endl;
	}
    return 0;
}


Measured memory_bytes: 1192
#include<stdio.h>
#include<algorithm>
#define MAX 101
using namespace std;

typedef struct Matrix {
    int r, c;
} Matrix;

Matrix M[MAX];

int Matrix_Chain_Multiplication(int n) {
    int m[MAX][MAX];
    
    if (n==1) return 0;

    for (int i=1; i<=n; i++) {
        m[i][i] = 0;
    }
    
    for (int i=1; i<n; i++) {
        m[i][i+1] = M[i].r*M[i].c*M[i+1].c;
    }

    for (int k=2; k<n; k++) {
        for (int i=1; i+k<=n; i++) {
            m[i][i+k] = (1 << 21);
            for (int j=i; j<i+k; j++) {
                m[i][i+k] = min(m[i][i+k], m[i][j]+m[j+1][i+k]+M[i].r*M[j].c*M[i+k].c);
            }
        }
    }

    return m[1][n];
}

int main() {
    int n;
    
    scanf("%d", &n);
    for (int i=1; i<=n; i++) scanf("%d %d", &M[i].r, &M[i].c);
    
    int minimum = Matrix_Chain_Multiplication(n);

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

    return 0;
}


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

int main() {
  int n;
  cin >>n;
  vector<int>a(n);
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  bool iro1=false;
  bool iro2=false;
  bool iro3=false;
  bool iro4=false;
  bool iro5=false;
  bool iro6=false;
  bool iro7=false;
  bool iro8=false;
  bool iro9=false;
  int count=0;
  for(int i=0;i<n;i++){
    if(a[i]<400){
      iro1=true;
    }else if(a[i]<800){
      iro2=true;
    }else if(a[i]<1200){
      iro3=true;
    }else if(a[i]<1600){
      iro4=true;
    }else if(a[i]<2000){
      iro5=true;
    }else if(a[i]<2400){
      iro6=true;
    }else if(a[i]<2800){
      iro7=true;
    }else if(a[i]<3200){
      iro8=true;
    }else {
      iro9=true;
      count++;
    }
  }
  int kotae=iro1+iro2+iro3+iro4+iro5+iro6+iro7+iro8;
  if(kotae==0&&iro9==true){
    cout<<1<<" "<<count<<endl;
  }else if(kotae!=0&&iro9==true){    
    cout<<kotae<<" "<<kotae+count<<endl;
  }else{
    cout<<kotae<<" "<<kotae<<endl;
  }
  return 0;
}

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

#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))

int main()
{
	int N;
	int B[100000];
	int A[100000];
	int sum = 0;

	scanf("%d", &N);

	for (int i = 0; i < N - 1; i++)
		scanf("%d", &B[i]);

	A[0] = B[0];

	int tmp;

	for (int i = 1; i < N - 1; i++)
	{
		tmp = max(B[i - 1], A[i - 1]);
		A[i] = min(tmp, B[i]);
	}
	A[N - 1] = max(B[N - 2], A[N - 2]);

	for (int i = 0; i < N; i++)
	{

		//printf("%d\n", A[i]);
		sum += A[i];
	}
	printf("%d", sum);

}

Measured memory_bytes: 128
import sys
import collections
import heapq
input = sys.stdin.readline


# 操作の回数 n を a, b, cd の３つに分割する
def f(n):
    a = []
    for i in range(n+1):
        for j in range(i, n+1):
            a.append((i, j-i, n-j))
    return(a)


def main():
    N, K = map(int, input().split())
    V = list(map(int, input().split()))
    ans = 0
    for a, b, cd in f(K):
        H = []
        D = collections.deque(V)
        for i in range(a):
            if not D:
                break
            heapq.heappush(H, D.popleft())
        for i in range(b):
            if not D:
                break
            heapq.heappush(H, D.pop())
        for i in range(cd):
            if not H or H[0] >= 0:
                break
            heapq.heappop(H)
        ans = max(ans, sum(H))
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 56796
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int ABS=2e3; 
const int maxn=4e3+10;
int dp[maxn][maxn];
int st[maxn][maxn];
int ed[maxn][maxn];
int ans=0;
int n;
int inv[maxn*2],fact[maxn*2];
int Pow(int a,long long k)
{
	int ret=1;
	while(k)
	{
		if(k&1)ret=ret*1LL*a%mod;
		a=a*1LL*a%mod,k>>=1;
	}
	return ret;
}
int C(int x,int y){return fact[x]*1LL*inv[x-y]%mod*inv[y]%mod;}
int main()
{
	scanf("%d",&n),fact[0]=inv[0]=1;
	for(int i=1;i<=8000;i++)fact[i]=fact[i-1]*1LL*i%mod,inv[i]=Pow(fact[i],mod-2);
	for(int i=1;i<=n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		st[ABS-x][ABS-y]++;
		ed[ABS+x][ABS+y]++;
		ans=(ans-C(x*2+y*2,y*2)+mod)%mod;
	}
	for(int i=0;i<=4000;i++)
	for(int j=0;j<=4000;j++)
	{
		dp[i][j]=(st[i][j]*1LL+(i==0?0:dp[i-1][j])+(j==0?0:dp[i][j-1]))%mod;
		ans=ans+dp[i][j]*1LL*ed[i][j]%mod,ans%=mod;
	}
	printf("%d\n",ans*1LL*Pow(2,mod-2)%mod);
}


Measured memory_bytes: 127232