akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

long long int N, t[114], v[114], R[252525], a, i;

int main(){
    scanf("%lld", &N);
    *t = 0;
    *v = 0;
    for(; i < N; ++i){scanf("%lld", t + i + 1);t[i + 1] *= 2;}
    for(i = 0; i < N; ++i){scanf("%lld", v + i + 1);v[i + 1] *= 2;}
    t[N + 1] = 0;
    v[N + 1] = 0;
    partial_sum(t, t + N + 2, t);
    for(i = 1; i <= t[N + 1]; ++i){
        R[i] = 1145141919810LL;
        for(int j = 0; j <= N + 1; ++j){
            R[i] = min(abs(min({t[j] - i, 0LL, j ? i - t[j - 1] : 0LL})) + v[j], R[i]);
        }
    }
    for(i = 1; i <= t[N + 1]; ++i){
        a += (R[i] + R[i - 1]);
    }
    a >>= 1;
    printf("%lld", a / 4);
    switch(a & 3){
    case 1:
        puts(".25");
        break;
    case 2:
        puts(".5");
        break;
    case 3:
        puts(".75");
        break;
    }
    return 0;
}


Measured memory_bytes: 512
import copy

k = int(input())

lun = [1,2,3,4,5,6,7,8,9]
tlun = []
tlun = copy.deepcopy(lun)
length = 2
while len(lun) < k:
    tmp = []
    for x in tlun:
        y = str(x)
        xt = int( y[-1] )
        a = xt + 1
        b = xt - 1
        if a != 10:
            lun.append(int(y+str(a)))
            tmp.append(int(y+str(a)))
        
        if b != -1:
            lun.append(int(y+str(b)))
            tmp.append(int(y+str(b)))
        
        lun.append(int(y+str(xt)))
        tmp.append(int(y+str(xt)))
    tlun = copy.deepcopy(tmp)

lun.sort()
print(lun[k-1])
        

    






Measured memory_bytes: 19728
function Main(input) {
	var inputArr = input.split("\n");
	var knArr = inputArr[0].split(" ");
	var n = parseInt(knArr[0], 10);
	var k = parseInt(knArr[1], 10);
  　inputArr.shift();
  	var list = inputArr
    	.filter(i => i !== '')
    	.sort(function(a, b){return a-b;});
    var min = 10000000000;
	for(var i = 0; i < n - k + 1; i++) {
      var p = list[i + k - 1] - list[i];
      min = p < min ? p : min;
	}
    console.log(min);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

int main() {
  int N, K, X, Y;
  cin >> N >> K >> X >> Y;
  
  if(N > K) {
    cout << (X * K) + (N - K) * Y << endl;
  } else {
    cout << N * X << endl;
  }

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,c,x,y,ans;
int main() {
	//freopen("1.txt","r",stdin);
	scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&x,&y);
	ans=1LL<<60;
	for (int ab=0;ab<=max(x,y);ab++) {
		ll A=max(0LL,x-ab),B=max(0LL,y-ab);
		ll tmp=A*a+B*b+ab*2*c;
		ans=min(ans,tmp);
	}
	printf("%lld\n",ans);
	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++)
#define all(x) x.begin(),x.end()

int main() {
  int n;
  cin >> n;
  int sum=0,a=n;
  while(a){
     sum+=a%10;
     a/=10;
  }
  cout << (n%sum==0 ? "Yes" : "No") << endl;
}

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

int n;

void link(int x, int y) { std::cout << x << ' ' << y << '\n'; }

int main() {
	std::ios::sync_with_stdio(0), std::cin.tie(0);
	std::cin >> n;
	if (!(n & n - 1))
		return std::cout << "No\n", 0;
	std::cout << "Yes\n";
	link(1, 3), link(3, 2), link(2, n + 1), link(n + 1, n + 3), link(n + 3, n + 2);
	for (int i = 4; i < n; i += 2)
		link(1, i + 1), link(i + 1, i), link(1, i + n), link(i + n, i + n + 1);
	if (!(n & 1)) {
		int p = 1 << 31 - __builtin_clz(n);
		link(n, p + n), link(n + n, n - p + 1);
	}
	return 0;
}

Measured memory_bytes: 2304
#include <bits/stdc++.h>
#define SPEED ios::sync_with_stdio(false); cin.tie(0)
#define loop(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<long long int,long long int>
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define mo 1000000007
#define INF 1e18
#define eps 0.0000000001
#define stp setprecision(20)
#define endl '\n'
using namespace std;
//mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());

#define N  int(2e5)+10

int main()
{    SPEED;

       int n,k;
       cin>>n>>k;
       int maxi,mini ;
       if(k==1)
        {
        	  cout<<0;return 0;
		}
		else 
		{
			  cout<< (n-k);
		}
}




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

typedef long long ll;
#define rep(i,x) for(int i=0;i<x;i++)
#define put(ans)    cout << ans << endl;

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

    int t[n],ans(0);
    rep(i,n){
        cin >> t[i];
        ans += t[i];
    }

    int m;  cin >> m;

    rep(i,m){
        int p,x;
        cin >> p >> x;
        ans -= t[p-1]-x;
        cout << ans << endl;

        ans += t[p-1]-x;
    }

    return 0;
}

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

const string a = "Hoshino";
const string b = "Hoshina";
int n;
string str;

int main()
{
	cin >> n;
	cin.get();
	while (n--)
	{
		getline(cin, str);
		for (int i = 0; i <= (int)str.size() - (int)a.size(); i++)
		{
			if (str.substr(i, a.size()) == a) str.replace(i, b.size(), b);
		}
		cout << str << endl;
	}

	return 0;
}

Measured memory_bytes: 3168
N,M = map(int,input().split())

A = []
for i in range(N):
  A.append(input())
B = []
for i in range(M):
  B.append(input()) 

ans = "No"
for i in range(N-M+1):
  for j in range(N-M+1):
    if A[i][j:j+M] == B[0]:
      cnt = 0
      for k in range(1,M):
        if A[i+k][j:j+M] == B[0+k]:
          continue
        else:
          cnt =1
          break
      if cnt == 0:
        ans = "Yes"
print(ans)        

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

int main()
{
    int N;
    cin >> N;
    int *a = new int [N+2];
    a[0] = a[N+1] = 0;
    for(int i=1;i<N+1;i++){
        cin >> a[i];
    }
    int sum = 0;
    for(int i=0;i<N+2;i++) sum += abs(a[i+1] - a[i]);
    for(int i=1;i<N+1;i++){
        int ans = sum;
        ans += - abs(a[i] - a[i-1]) - abs(a[i+1] - a[i]) + abs(a[i+1] - a[i-1]);
        cout << ans <<endl;
    }

    return 0;
}


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

int main() {
  int h,w;
  cin>>h>>w;
  vector<vector<char>>a(h,vector<char>(w));
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++) cin>>a[i][j];
  }
  vector<bool>gyo(h);
  vector<bool>row(w);
  for(int i=0;i<h;i++) gyo[i]=false;
  for(int i=0;i<w;i++) row[i]=false;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(a[i][j]=='#') gyo[i]=true;
    }
  }
  for(int j=0;j<w;j++){
    for(int i=0;i<h;i++){
      if(a[i][j]=='#') row[j]=true;
    }
  }
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(gyo[i] && row[j]) cout<<a[i][j];
      if(j==w-1) cout<<endl;
    }
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,s,e) for(int i=(s); i<(e);i++)
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n)
#define repe(i,n) for(auto &&i:n)
#define all(v) (v).begin(),(v).end()
#define decimal fixed<<setprecision(20)
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
using namespace std;
using LL = long long;
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; }
const int INF = 1e9;
const LL LLINF = 1e16;

int main(){
    fastcin();
    LL n, k;
    cin >> n >> k;
    vector<LL> a(n+1, 0);
    LL ans = 0;
    map<LL, int> mp;
    mp[0]=1;
    rep(i, n){
        cin >> a[i+1];
        a[i+1] += a[i]+k-1;
        
        if(i+1-k >= 0) mp[a[i+1-k]%k]--;
        ans += mp[a[i+1]%k];
        mp[a[i+1]%k]++;
        // cout << ans << endl;
    }
    cout << ans << endl;

}


Measured memory_bytes: 14336
#include<bits/stdc++.h>
using namespace std;
pair<int,int> a[100000];
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].first;
		a[i].second=i;
	}
	sort(a,a+n);
	int cnt=0;
	for(int i=0;i<n;i++)
		cnt+=(i+a[i].second)&1;
	cout<<(cnt>>1)<<endl;
}


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

int n, a[100001];

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

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

    int f, t;
    f = t = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] % 4  == 0) f++;
        else if (a[i] % 2 == 0) t++;
    }

    if (f >= n / 2 or n - 2 * f <= t) {
        cout << "Yes" << endl;
    }
    else cout << "No" << endl;

    return 0;
}

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll i;
    string s;
    cin>>s;
    for(i=0;i<s.length();i++)
    {
        if(i%2==0)
        {
            if(s[i]=='L')
            {
                cout<<"No";
            break;
            }
        }
        else
        {
            if(s[i]=='R')
            {
                cout<<"No";
            break;
            }
            
        }
    }
    if(i==s.length())
    cout<<"Yes";

     

  return 0;
    
}
    


Measured memory_bytes: 384
import itertools
N,M,Q=map(int,input().split())

abcd_dic={}
for i in range(Q):
  a,b,c,d=map(int,input().split())
  abcd_dic[(a,b,c)]=d
#print(abcd_dic)

max_answer=0
for perm in itertools.combinations_with_replacement(range(1,M+1),N):
  #print(perm)
  answer=0

  for i in range(N):
    for j in range(i+1,N):
      diff=perm[j]-perm[i]
      if (i+1,j+1,diff) in abcd_dic:
        answer+=abcd_dic[(i+1,j+1,diff)]
        
  max_answer=max(answer,max_answer)
  
print(max_answer)

Measured memory_bytes: 9220
#include <iostream>
#include <vector>
#include <queue>
#include <sstream>
#include <algorithm>
#include <bitset>
#include <limits>
#include <map>
#include <set>
#include <iomanip>
#include <cmath>

using namespace std;

typedef long long int ll;
typedef std::numeric_limits<double> dbl;
const long long int LL_INF=1LL<<60;

vector<string> split(const string& input, char delimiter)
{
    stringstream stream(input);
    
    string field;
    vector<string> result;
    while (getline(stream, field, delimiter)) {
        result.push_back(field);
    }
    return result;
}

//#define DEBUG

ll A, B, M, N, D, K, L, Q, W, H, T, X, Y, S;

int main()
{
    string str; cin >> str;
    vector<char> out;
    for (auto s : str) {
        if (s == 'B')
            if (!out.empty())
                out.pop_back();
            else;
        else
            out.push_back(s);
    }

    for (auto o : out)
        cout << o;
    cout << endl;

    return 0;
}

Measured memory_bytes: 256
from collections import deque


def main():
    n, m = map(int, input().split())

    adj = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        adj[a].append(b)
        adj[b].append(a)

    ans = [0 for _ in range(n)]
    for _ in range(m):
        p, x = map(int, input().split())
        p -= 1
        ans[p] += x

    q = deque()
    q.append(0)
    visited = [False] * n
    visited[0] = True

    while q:
        u = q.pop()
        for v in adj[u]:
            if visited[v]:
                continue
            ans[v] += ans[u]
            q.append(v)
            visited[v] = True

    print(*ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 125756
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

void dfs(vector<vector<int>> &g, vector<int> &color, int cv, int col){
  color[cv] = col;
  int ncol = col^1;
  for(auto nv:g[cv]){
    if(color[nv]!=-1) continue;
    else{
      color[nv] = ncol;
      dfs(g,color,nv,ncol);
    }
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  int n;
  cin >> n;
  vector<vector<int>> g(n,vector<int>());
  rep(i,n-1){
    int a,b;
    cin >> a >> b;
    --a;--b;
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }
  vector<int> color(n,-1);
  dfs(g,color,0,0);
  int cb,cw;
  cb = cw = 0;
  rep(i,n){
    if(color[i]) cb++;
    else cw++;
  }
  // cb>=cw
  // 1 >= 0
  if(cb<cw){
    swap(cb,cw);
    rep(i,n) color[i] = color[i] ^ 1;
  }
  vector<int> ans(n);  
  if(cb >=cw*2){
    int san = 3;
    int el = 1;
    rep(i,n){
      if(color[i]==0) {
        ans[i] = san;
        san += 3;
      }
      else{
        if(el<=n){
          ans[i] = el;        
          if(el%3==1) el++;
          else el += 2;
        }
        else{
          ans[i] = san;
          san += 3;
        }
      }
    }
  }
  else{
    int san = 3;
    int el1 = 1;
    int el2 = 2;
    rep(i,n){
      if(color[i]==0){
        if(el2<=n){
          ans[i] = el2;
          el2 += 3;
        }
        else{
          ans[i] = san;
          san += 3;
        }
      }
      else{
        if(el1<=n){
          ans[i] = el1;
          el1 += 3;
        }
        else{
          ans[i] = san;
          san += 3;
        }
      }
    }
  }
  rep(i,n) cout << ans[i] <<" \n"[i==n-1];
  
  return 0;
    

}


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

using i64 = int_fast64_t;
using f64 = double;

i64 h, w;
vector<string> s;
vector<vector<i64>> dp;

i64 dfs(i64 y = 0, i64 x = 0) {
    if (dp[y][x] != -1) return dp[y][x];
    i64 res = INT64_MAX / 2;
    if (y + 1 < h) res = min(res, (s[y][x] == '#' && s[y + 1][x] == '.') + dfs(y + 1, x));
    if (x + 1 < w) res = min(res, (s[y][x] == '#' && s[y][x + 1] == '.') + dfs(y, x + 1));
    return dp[y][x] = res;
}

void solve() {
    cin >> h >> w;
    s.assign(h, "");
    for (auto& e : s) cin >> e;
    dp.assign(h, vector<i64>(w, -1));
    dp[h - 1][w - 1] = s[h - 1][w - 1] == '#';
    cout << dfs() << endl;
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
}


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

#define vec              vector<int>
#define vecll            vector<ll>
#define vecd             vector<double>
#define vecst            vector<string>
#define vecb             vector<bool>
#define v2(v,n,m,init)   vector<vector<int>>  v(n, vector<int>(m, init))
#define vb2(v,n,m,init)  vector<vector<bool>> v(n, vector<bool>(m, init))
#define vll2(v,n,m,init) vector<vector<ll>>   v(n, vector<ll>(m, init))

#define rep(i,n)         for(ll i=(ll)0; i<(ll)n; i++)
#define REP(i,m,n)       for(ll i=(ll)m; i<(ll)n; i++)
#define arr(var, n)      vec var(n); rep(i,n){cin >> var[i];}
#define arrll(var, n)    vecll var(n); rep(i,n){cin >> var[i];}
#define arrst(var, n)    vecst var(n); rep(i,n){cin >> var[i];}
#define all(var)         (var).begin(), (var).end()
#define sortall(var)     sort(all(var))
#define uniqueall(v)     v.erase(unique(v.begin(), v.end()), v.end());
#define pb(var)          push_back(var)
#define prt(var)         cout << (var) << "\n"
#define prtd(n, var)     cout << fixed << setprecision(n) << (var) << "\n"
#define prtfill(n, var)  cout << setw(n) << setfill('0') << (var);
#define prt2(v1, v2)     cout << (v1) << " " << (v2) << "\n"
#define prt3(v1, v2, v3) cout << (v1) << " " << (v2) << " " << (v3) << "\n"
#define prtall(v)        rep(i,v.size()){cout<<v[i]<<(i!=v.size()-1?" ":"\n");}
template <typename T>
bool chmax(T &a, const T& b){if(a<b){a=b; return true;} return false;}
template <typename T>
bool chmin(T &a, const T& b){if(a>b){a=b; return true;} return false;}
//----------------------------------------------------------------

int main(void) {
  int R, C, K;
  cin >> R >> C >> K;
  vll2(item, R+1, C+1, -1);
  rep(i,K){
    int a, b;
    ll v;
    cin >> a >> b >> v;
    item[a][b] = v;
  }

  vector<vector<vector<ll>>> dp(R+1, vector<vector<ll>>(C+1, vector<ll>(4, 0)));

  REP(i,1,R+1){
    REP(j,1,C+1){
      ll tmp=0;
      rep(k,4){chmax(tmp, dp[i-1][j][k]);}
      chmax(dp[i][j][0], tmp);
      if(item[i][j]>0) chmax(dp[i][j][1], tmp+item[i][j]);

      rep(k,4){
        chmax(dp[i][j][k], dp[i][j-1][k]);
        if(k!=0 && item[i][j]>0){
          chmax(dp[i][j][k], dp[i][j-1][k-1]+item[i][j]);
        }
      }
    }
  }

  ll ans=0;
  rep(i,4){
    chmax(ans, dp[R][C][i]);
  }
  prt(ans);
}


Measured memory_bytes: 707524
#include <cstdio>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

int main()
{
    for(;;){
        int t, n;
        cin >> t >> n;
        if(t == 0)
            return 0;

        for(int i=0; i<n; ++i){
            int s, f;
            cin >> s >> f;
            t -= f - s;
        }

        if(t <= 0)
            cout << "OK" << endl;
        else
            cout << t << endl;
    }
}

Measured memory_bytes: 0
#include <stdio.h>
#include <string.h>
  
int main(void){
    char b[65];
    char p[7][33] = {
        "1100000011",
        "1000000010000000100000001",
        "1111",
        "1000000110000001",
        "11000000011",
        "100000001100000001",
        "110000011",
    };
    char *bi;
  
    int i,t = 0;
    while(1){
        if(scanf("%s", b) == EOF){ break; }
        for(i=1; i<8; i++){
            scanf("%s", b+i*8);
        }
        bi = strchr(b, '1');
        for(i=0; i<7; i++){
            if(memcmp(bi, p[i], strlen(p[i])) == 0){
                printf("%c\n", 'A' + i);
                break;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 568
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int main(){
    int n;
    cin >> n;
    double x, y, D_1 = 0, d_2 = 0, D_2, d_3 = 0, D_3, D_max = 0;
    
    int x_vector[1000];
    int y_vector[1000];
    for(int i=0; i<n; i++){
        cin >> x;
        x_vector[i] = x;
    }
    for(int i=0; i<n; i++){
        cin >> y;
        y_vector[i] = y;
    }
    for(int i=0; i<n; i++){
        double t;
        t = fabs(x_vector[i] - y_vector[i]);
        D_1 += t;
        d_2 += pow(t, 2.0);
        d_3 += pow(t, 3.0);
        if (t > D_max) D_max = t;
    }
    D_2 = sqrt(d_2);
    D_3 = cbrt(d_3);
    printf("%lf\n", D_1);
    printf("%lf\n", D_2);
    printf("%lf\n", D_3);
    printf("%lf\n", D_max);
    return 0;
}


Measured memory_bytes: 3492
i;j;x[9<<14];m=9<<25;main(){
for(;~scanf("%d",x+i++););
for(;j<x[0]-x[1]+1;j++)m=fmin(x[j+x[1]+1]-x[j+2]+fmin(abs(x[j+2]),abs(x[j+x[1]+1])),m);
printf("%d",m);
}

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


int main() {
	//code
	//cout<<"ashish"<<endl;
	int n;
	cin>>n;
	long long int a[n];
	long long int sum=0;
	map<int,int>m;
	for(int i=0;i<n;i++){
        cin>>a[i];
        m[a[i]]++;
        sum+=a[i];}
    int k;
    cin>>k;
    while(k--){
        long long int b,c;
        cin>>b>>c;
        sum=sum-(b*m[b]);
        sum=sum+(c*m[b]);
         m[c]=m[c]+m[b]; m[b]=0;
        cout<<sum<<endl;
    }
	return 0;
}


Measured memory_bytes: 8812
/**
*     => Md. Sajjat Hosen
*     => Department of Computer Science and Engineering
*     => Bangabandhu Sheikh Mujibur Rahman Science and Technology University
**/

/*..................! TRY ONCE MORE !..................*/

/*...Part - 01...*/

#include <bits/stdc++.h>
using namespace std ;

/*...Part - 02...*/

typedef long long               ll ;
typedef long double             ld ;
typedef unsigned long long      ull ;
typedef pair<int,int>           pii ;
typedef pair<ll,ll>             pll ;
typedef vector<int>             vi ;
typedef vector<ll>              vll ;
typedef vector<vector<int>>     vvi ;

int Int(){int x ; scanf("%d",&x) ; return x ;}
ll Long(){ll x ; scanf("%lld",&x) ; return x ;}
float Float(){float x ; scanf("%f",&x) ; return x ;}
double Double(){double x ; scanf("%lf",&x); return x;}

/*...Part - 03...*/
/*....Debugger....*/

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

/*...Part - 04...*/
/*...Needed to change according to problem requirements...*/

const int N          = (int)2e5 + 5 ;
const int maxN       = (int)1e6 + 6 ;
const ll  Mod        = (ll)1e9 + 7 ;
const int inf        = (int)2e9 ;
const ll  Inf        = (ll)1e18 ;

/*..........................................................*/
/*...Part - 05...*/

#define     Int         Int()
#define     Long        Long()
#define        Float         Float()
#define     Double         Double()
#define     all(x)      x.begin() , x.end()
#define     sz(x)       (int)x.size()
#define     mem(a)      memset(a , 0 ,sizeof a)
#define     memn(a)     memset(a , -1 ,sizeof a)

/*...Part - 06...*/
/*...... ! Code start from here ! ......*/

ll a[maxN];

int main(){
    //freopen("input.txt","r",stdin);
    int test = 1 , tc = 0 ;
    ll n, i, j, ans, l, r, mid, x = 0, y;
    while(test--){
        n = Long;
        for(i = 1; i <= n; i++){
            a[i] = Long;
        }
        sort(a + 1, a + n + 1);
        for(i = 1; i <= n; i++){
            for(j = i + 1; j <= n; j++){
                y = a[i] + a[j];
                ans = 0;
                l = 1;
                r = n;
                while(l <= r){
                    mid = (l + r) / 2;
                    if(a[mid] < y){
                         l= mid + 1;
                         ans = mid;
                    }
                    else{
                        r = mid - 1;
                    }
                }
                ans = ans - j;
                //if(ans <= 0) ans = 0;
                x += ans;
            }
        }
        printf("%lld\n", x);
    }
    return 0 ;
}

/*...Always look at the part - 04...*/
/*...............END................*/


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

using namespace std;
using LL = long long;
using P = pair<int, int>;

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

#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_v(size_t a, Ts... ts) {return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...)); }

template<typename T,typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v){ t = v; }

template<typename T,typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v){ for(auto &e : t) fill_v(e, v); }

const int INF = (int)1e9;
const LL INFL = (LL)1e18;
const int MOD = 1e9 + 7;

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;
    vector<int> d(n);
    REP(i, n) cin >> d[i];

    sort(all(d));
    cout << d[n/2] - d[n/2-1] << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using lli = int_fast64_t;
using ulli = uint_fast64_t;
#define debug(x) cerr << #x << " : " << x << endl
#define debugv(x) cerr << #x << " : {";for(auto value_of_x:x){ cerr << value_of_x << ", ";}cerr << endl
#define debugst(x) auto xt = x;cerr << #x << " : {";for(int i=0;i<x.size();i++){ cerr << xt.top() << ", ";xt.pop();}cerr << endl
#define debugvp(x) cerr << #x << " : {";for(auto value_of_x:x){ cerr << value_of_x.first << " : " << value_of_x.second << ", ";}cerr << endl

const lli MOD = 1000000007;
const lli LIMIT = 1000000000000000000 * 5;
const int tenfive = 100000;

int main() {
	lli L, R;
	cin >> L >> R;
	if (R - L >= 2019) {
		cout << 0 << endl;
		return 0;
	}
	L %= 2019;
	R %= 2019;
	lli ans = LIMIT;
	for (lli i = L; i <= R; i++) {
		for (lli j = i + 1; j <= R; j++) {
			ans = min(ans, (i * j) % 2019);
		}
	}
	cout << ans << endl;

 	return 0;
}


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

using namespace std;

typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = (ll)1e9 + 7;

int main()
{
  string w; cin >> w;
  int n = w.size();
  vector<int> freqs(128, 0);
  for (int i = 0; i < n; ++i) {
    ++freqs[w[i] - 'a'];
  }
  bool ok = true;
  for (int i = 0; i < 26; ++i) {
    if (freqs[i] & 1) {
      ok = false;
      break;
    }
  }
  printf("%s\n", ok ? "Yes" : "No");
  return 0;
}


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

using namespace std;

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

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

    return 0;
}


Measured memory_bytes: 888
def main():
    N, x = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    i = 0
    count = 0
    while i < N and x-A[i]>=0:
        count += 1
        x -= A[i]
        i += 1
    if x == 0:
        return count
    else:
        if i == N:
            return count - 1
        else:
            return count

if __name__ == '__main__':
    print(main())

Measured memory_bytes: 3060
#include <stdio.h>

int main(void){
    int n,k,map[100],i,o,q,sign;
    for(;sign=0,scanf("%d %d",&n,&k),k;){
        for(i=0;i<k;i++)
            scanf("%d",&map[i]);
        for(i=0;i<n;i++)
            for(o=0;o<k;o++){
                scanf("%d",&q);
                map[o]-=q;
            }
        for(i=0;i<k;i++)
            if(map[i]<0)
                sign=1;
        printf("%s\n",sign==0?"Yes":"No");
    }
    return 0;
}

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

#define ASC(vec) vec.begin(), vec.end()		// 昇順ソート 例：sort(ASC(vec));
#define DESC(vec) vec.rbegin(), vec.rend()	// 降順ソート 例:sort(DESC(vec));
#define rep(i, n) for(i = 0; i < n; i++)
#define Rep(i, n) for(i = 1; i < n; i++)
#define Ans(s) cout << s << endl;

const int inf = (int)1e9 + 7;
const long long INF = 1LL << 60;

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; }

int GCD(int a, int b) { return b ? GCD(b, a % b) : a; }

typedef long long ll;

// 4,8方向に探索する際に用いる配列
//int dx[4] = { 0,  0, 1, -1 };
//int dy[4] = { 1, -1, 0,  0 };
//int dx[8] = { 1, 0, -1,  0, 1, -1, -1,  1 };
//int dy[8] = { 0, 1,  0, -1, 1,  1, -1, -1 };

constexpr auto MAX = 100010;

int mod = 1000000007;

int main()
{
	int h, w;
	cin >> h >> w;

	vector<string> table(h);

	for (int y = 0; y < h; y++)
	{
		cin >> table[y];
	}

	vector<vector<int>> L(h, vector<int>(w));
	vector<vector<int>> R(h, vector<int>(w));
	vector<vector<int>> U(h, vector<int>(w));
	vector<vector<int>> D(h, vector<int>(w));

	for (int y = 0; y < h; y++)
	{
		for (int x = 0; x < w; x++)
		{
			if (table[y][x] == '#') L[y][x] = 0;
			else if (x == 0) L[y][x] = 1;
			else L[y][x] = L[y][x - 1] + 1;
		}
	}
	for (int y = h - 1; y >= 0; y--)
	{
		for (int x = w - 1; x >= 0; x--)
		{
			if (table[y][x] == '#') R[y][x] = 0;
			else if (x == w - 1) R[y][x] = 1;
			else R[y][x] = R[y][x + 1] + 1;
		}
	}
	for (int x = 0; x < w; x++)
	{
		for (int y = 0; y < h; y++)
		{
			if (table[y][x] == '#') U[y][x] = 0;
			else if (y == 0) U[y][x] = 1;
			else U[y][x] = U[y - 1][x] + 1;
		}
	}
	for (int x = w - 1; x >= 0; x--)
	{
		for (int y = h - 1; y >= 0; y--)
		{
			if (table[y][x] == '#') D[y][x] = 0;
			else if (y == h - 1) D[y][x] = 1;
			else D[y][x] = D[y + 1][x] + 1;
		}
	}

	int ans = 0;

	for (int y = 0; y < h; y++)
	{
		for (int x = 0; x < w; x++)
		{
			int tmp = L[y][x] + R[y][x] + U[y][x] + D[y][x] - 3;
			ans = max(ans, tmp);
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 67200
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cmath>
#include <string>
#include <stdlib.h>
#include <fstream>
#include <set>
#include <map>
#include <stack>
#include <deque>
#include <iterator>
#include <iomanip>
#include <queue>
using namespace std;



int main(){
  long long x, y, n;
  cin >> n >> x >> y;
  vector<vector<long long> > g(n + 1);
  for(int i = 1; i < n; ++i){
    g[i].push_back(i + 1);
    g[i + 1].push_back(i);
  }
  g[x].push_back(y);
  g[y].push_back(x);
  vector<vector<long long> > d(n + 1, vector<long long>(n + 1));
  for(int k = 1; k <= n; ++k){
    queue<int> q;
    q.push(k);
    vector<bool> used (n + 1);
    used[k] = true;
    while (!q.empty()) {
      int v = q.front();
      q.pop();
      for (size_t i = 0; i < g[v].size(); ++i) {
        int to = g[v][i];
        if (!used[to]) {
          used[to] = true;
          q.push(to);
          d[k][to] = d[k][v] + 1;
        }
      }
    }
  }
  vector<long long> ans(n + 1, 0);
  for(int i = 1; i <= n; ++i)
      for(int j = 1; j <= n; ++j){
        ans[d[i][j]]++;
      }
  for(int i = 1; i < n; ++i) cout << ans[i] / 2 << endl;
}

Measured memory_bytes: 31744
#include <iostream>
using namespace std;
int main(){
    int a,b ;
    cin >> a >> b;
    while(a != 0 || b != 0){
        for(int i=1 ;i<=a;i++){
            for(int w=1;w<=b;w++){
                cout << "#";
            }
            cout << endl;
        }
        cin >> a >> b;
        cout << endl;
    }
}


Measured memory_bytes: 3116
#include <iostream>

int main(){
   int N, X, Y;
   std::cin >> N >> X >> Y;

   int count[N];
   std::fill(count, count+N, 0);
   int d;
   for(int i=1; i<=N; ++i){
      for(int j=i+1; j<=N; ++j){
	 if(i<=X){
	    if(j<=X) d = j - i;
	    else if(j<=Y) d = X - i + std::min(j - X, 1 + Y - j);
	    else d = X - i + 1 + j - Y;
	 }else if(i<=Y){
	    if(j<=Y) d = std::min(j - i, i - X + 1 + Y - j);
	    else d = j - Y + std::min(Y - i, i - X + 1);
	 }else{
	    d = j - i;
	 }
	 ++count[d];
      }
   }
   for(int k=1; k<N; ++k){
      std::cout << count[k] << std::endl;
   }
   return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <array>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <cctype>
#include <map>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <queue>


#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

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


using namespace std;

bool is_integer( float x ){
    return floor(x)==x;
}


int main() {
    int x; cin >> x;
    int m,d;
    d = x%100;
    m = x/100;

    for(int i = 0; i < m; i ++){
        if(d >= 5) d-= 5;
        else if(d >= 4) d-= 4;
        else if(d >= 3) d-= 3;
        else if(d >= 2) d-= 2;
        else if(d >= 1) d-= 1;
    }

    cout << ((d == 0)?1:0);
    return 0;
}











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

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

    if (a <= 5){
      cout << 0;
    }else if (a <= 12){
      cout << (b/2);
    }else{
      cout << b;
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
int K;
  string S;
  cin>>K>>S;
 if(S.size() <= K){
 cout<<S;
 }
  else{
   for(int i=0;i<K;i++){
   cout<<S.at(i);
   }
    cout<<"...";
  }
}

Measured memory_bytes: 3592
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxx = 1000000;
int K,X;
int main() {
    scanf("%d%d",&K,&X);
    for (int i = max(-maxx,X-K+1);i <= min(maxx,X+K-1);i++) printf("%d ",i); printf("\n");
}


Measured memory_bytes: 128
a, b, m = map(int, input().split())
a_price = list(map(int, input().split()))
b_price = list(map(int, input().split()))
coupon = []
for _ in range(m):
    coupon.append(list(map(int, input().split())))

a_copy = a_price.copy()
a_copy.sort()
b_copy = b_price.copy()
b_copy.sort()
a_min = a_copy[0]
b_min = b_copy[0]
min = a_min + b_min
totals = [min]
for list in coupon:
    tmp = a_price[list[0] - 1] + b_price[list[1] - 1] - list[2]
    totals.append(tmp)

totals.sort()
ans = totals[0]

print(ans)


Measured memory_bytes: 44276
#include <bits/stdc++.h>
typedef long long ll;
#define MOD 1000000007
#define INF -99999999 
using namespace std;

char maze[100][100];
int dist[100][100];

int main(){
    int H,W; cin >> H >> W;
    int sy,sx,gy,gx;
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            cin >> maze[i][j];
        }       
    }
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    int ans = 0;

    for (int sy = 0; sy < H; sy++)
    {
        for (int sx = 0; sx < W; sx++)
        {
            for (int gy = 0; gy < H; gy++)
            {
                for (int gx = 0; gx < W; gx++)
                {
                    if(maze[sy][sx] != '.' || maze[gy][gx] != '.') continue;
                    for (int i = 0; i < H; i++)
                    {
                        for (int j = 0; j < W; j++)
                        {
                            dist[i][j] = INF;
                        }
                    }       
                    queue<pair<int,int>> que;
                    while(!que.empty()){
                        que.pop();
                    }
                    que.push(make_pair(sx,sy)); // queにスタート地点を入れる
                    dist[sy][sx] = 0; //スタートからスタートの距離は０
                    while(!que.empty()){ // queが空になるまで行う
                        pair<int,int> p = que.front(); // pはqueの最初の要素
                        que.pop(); // pに入れたものを消す
                        int x=p.first;
                        int y=p.second;
                        if(x==gx&&y==gy) break; //ゴールに到達していたら終了
                        for(int i=0;i<4;i++){
                            int mx=x+dx[i];
                            int my=y+dy[i]; //縦横に動く
                            if( mx < 0 || my < 0 || mx >= W || my >= H ) continue;
                            if(maze[my][mx]!='#'&&dist[my][mx]==INF){ //距離が決定されていない(未訪)
                                que.push(make_pair(mx,my)); //次の座標をqueに入れる
                                dist[my][mx] = dist[y][x] + 1;
                            }
                        }
                    }
                    ans = max(ans,dist[gy][gx]);
                }
                
            }
            
        }
        
    }
      
    cout<< ans <<endl;
    
}

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

int main() {
	int x, y;
	while (1) {
		cin >> x >> y;
		if ((x == 0) && (y == 0)) break;
		if (x > y) swap(x, y);
		cout << x << " " << y << "\n";
	}
	return 0;
}


Measured memory_bytes: 3044
import numpy as np

N = int(input())
A = np.zeros((N,2))

for i in range(N):
	A[i, 0], A[i, 1] = [int(j) for j in input().split()]

A = A[np.argsort(A[:,1]), :]

for i in range(N-1):
	A[i+1, 0] = A[i, 0]+A[i+1, 0]

ans = ['Yes', 'No']
t = np.sum((A[:,1]-A[:,0])<0)

print(ans[t>0])


Measured memory_bytes: 21272
s=input()

r3=s.count('RRR')
if r3==1:
    print(3)
    exit(0)
r2=s.count('RR')

if r2==1:
    print(2)
    exit(0)

r=s.count('R')

if r>=1:
    print(1)
else:
    print(0)


Measured memory_bytes: 8964
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define between(a,x,b) ((a)<=(x)&&(x)<=(b))
#define MAX 123456
using namespace std;
vector<int>p(MAX*2+1);
int main(){
  p[0] = p[1] = 1;
  REP(i, 2, MAX+1)
    if(!p[i])
       for(int j = i*2; j <= MAX*2; j+=i) 
	 p[j] = 1;
  int n;
  while(scanf("%d", &n) && n){
    int res = 0;
    for(int i = n+1;i <= 2 * n; i++) if(!p[i]) res++;
    printf("%d\n", res);
  }
  return 0;
}

Measured memory_bytes: 2060
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<ll> vl;
typedef pair<ll, ll> PP;
#define rep(i, n) for (ll i = 0; i < ll(n); i++)
#define all(v) v.begin(), v.end()
#define inputv(v, n)    \
    vl v;               \
    rep(i, n)           \
    {                   \
        ll x;           \
        cin >> x;       \
        v.push_back(x); \
    }
const ll INF = 999999999999999;
const ll MOD = 1000000007;
ll a, b, c, d, e, f, p, t, x, y, z, q, m, n, r, h, k, w, l, ans = 0;
int main()
{
    string S;
    cin>>n;
    map<string,ll> M;
    vector<pair<string,ll>> V;
    rep(i,n){
        cin>>S;
        cin>>t;
        V.push_back({S,t});
    }

    reverse(all(V));

    a=0;
    rep(i,n){
        M[V[i].first]=a;
        a+=V[i].second;
    }

    cin>>S;
    cout<<M[S]<<endl;
}

Measured memory_bytes: 256
-- https://github.com/minoki/my-atcoder-solutions
{-# LANGUAGE BangPatterns #-}
import Data.Int (Int64)
import Data.Coerce
import qualified Data.ByteString.Char8 as BS
import Control.Exception (assert)

main = do
  n <- readLn
  s <- BS.getLine
  assert (BS.length s == 2 * n) $ return ()
  let loop :: N -> Int -> Int -> N
      loop !acc !k !i | BS.length s == i = if k == 0 then acc else 0
                      | BS.index s i == 'W' = if even k
                                              then loop (acc * fromIntegral k) (k-1) (i+1)
                                              else loop acc (k+1) (i+1)
                      | otherwise = if even k
                                    then loop acc (k+1) (i+1)
                                    else loop (acc * fromIntegral k) (k-1) (i+1)
  print $ loop (product $ map fromIntegral [1..n]) 0 0

--
-- Modular Arithmetic
--

modulo :: Int64
modulo = 10^9+7
addMod, subMod, mulMod :: Int64 -> Int64 -> Int64
addMod !x !y | x + y >= modulo = x + y - modulo
             | otherwise = x + y
subMod !x !y | x >= y = x - y
             | otherwise = x - y + modulo
mulMod !x !y = (x * y) `rem` modulo

newtype N = N { unwrapN :: Int64 } deriving (Eq)
instance Show N where
  show (N x) = show x
instance Num N where
  (+) = coerce addMod
  (-) = coerce subMod
  (*) = coerce mulMod
  fromInteger = fromInteger_N
  abs = undefined; signum = undefined
  {-# INLINE fromInteger #-}

fromInteger_N :: Integer -> N
fromInteger_N n = N (fromInteger (n `mod` fromIntegral modulo))
{-# INLINE [1] fromInteger_N #-}

fromIntegral_Int64_N :: Int64 -> N
fromIntegral_Int64_N n | 0 <= n && n < modulo = N n
                       | otherwise = N (n `mod` modulo)

fromIntegral_Int_N :: Int -> N
fromIntegral_Int_N n | 0 <= n && fromIntegral n < modulo = N (fromIntegral n)
                     | otherwise = N (fromIntegral n `mod` modulo)

{-# RULES
"^9/Int" forall x. x ^ (9 :: Int) = let u = x; v = u * u * u in v * v * v
"^9/Integer" forall x. x ^ (9 :: Integer) = let u = x; v = u * u * u in v * v * v
 #-}

{-# RULES
"fromIntegral/Int->N" forall x. fromInteger_N (fromIntegral x) = fromIntegral_Int_N x
"fromIntegral/Int64->N" forall x. fromInteger_N (fromIntegral x) = fromIntegral_Int64_N x
 #-}


Measured memory_bytes: 1404
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		String[] arrStrL = (new BufferedReader(new InputStreamReader(System.in))).readLine().split(" ");
		int a = Integer.parseInt(arrStrL[0]);
		int b = Integer.parseInt(arrStrL[1]);

		System.out.println((a * b) + " " + (2 * a + 2 * b));
	}
}

Measured memory_bytes: 24152
#include<stdio.h>
#include<string>
#include<iostream>
using namespace std;
struct SK{int N;int S;int E;int W;int T;int B;};
void north(struct SK SA);
void south(struct SK SA);
void east(struct SK SA);
void west(struct SK SA);


void right(struct SK SA);
void left(struct SK SA);

int main(){
struct SK SA;
int N;char ch;
int c=0;int k=0;
string SR;

while(1){

scanf("%d",&N);
if(N==0)break;
c=1;k=0;
SA.T=1;
SA.S=2;
SA.B=6;
SA.N=5;
SA.E=3;
SA.W=4;
for(int i=0;i<N;i++)

{
//scanf("%c",&ch);
	cin>>SR;
	if(SR=="North"){int t=0;t=SA.T;SA.T=SA.S;SA.S=SA.B;SA.B=SA.N;SA.N=t;}
//else if(ch=="N")north(SA);
else if(SR=="East"){int t=0;t=SA.T;SA.T=SA.W;SA.W=SA.B;SA.B=SA.E;SA.E=t;}
else if(SR=="West"){int t=0;t=SA.T;SA.T=SA.E;SA.E=SA.B;SA.B=SA.W;SA.W=t;}
else if(SR=="South"){int t=0;t=SA.T;SA.T=SA.N;SA.N=SA.B;SA.B=SA.S;SA.S=t;}
else if(SR=="Right"){int t=0;t=SA.N;SA.N=SA.W;SA.W=SA.S;SA.S=SA.E;SA.E=t;}
else if(SR=="Left"){int t=0;t=SA.N;SA.N=SA.E;SA.E=SA.S;SA.S=SA.W;SA.W=t;}
c+=SA.T;//k++;cout<<SA.T;
}
printf("%d\n",c);
}
return 0;
}

void north(struct SK SA){
int t=0;t=SA.T;SA.T=SA.S;SA.S=SA.B;SA.B=SA.N;SA.N=t;
}
void south(struct SK SA){
int t=0;t=SA.T;SA.T=SA.N;SA.N=SA.B;SA.B=SA.S;SA.S=t;
}
void east(struct SK SA){
int t=0;t=SA.T;SA.T=SA.W;SA.W=SA.B;SA.B=SA.E;SA.E=t;
}
void west(struct SK SA){
int t=0;t=SA.T;SA.T=SA.E;SA.E=SA.B;SA.B=SA.W;SA.W=t;
}


void right(struct SK SA){
int t=0;t=SA.N;SA.N=SA.W;SA.W=SA.S;SA.S=SA.E;SA.E=t;
}
void left(struct SK SA){
int t=0;t=SA.N;SA.N=SA.E;SA.E=SA.S;SA.S=SA.W;SA.W=t;
}

Measured memory_bytes: 1248
while 1:
    nums = int(input())
    if nums != 0:
        d = {}
        stars = list(map(int,input().split()))
        for x in stars:
            if x not in d:
                d[x] = 1
            else:
                d[x] += 1

        key = list(d.keys())
        val = list(d.values())
        m = int(max(val))
        if m > nums/2:
            res = key[val.index(m)]
            print(res)
        else:
            print("NO COLOR")
    else:break

Measured memory_bytes: 126912
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    k, t = LI()
    a = LI()
    dp = [0] * (k + 1)
    l = r = 0
    dp[0] = 1
    for ai in a:
        for i in range(k, ai - 1, -1):
            dp[i] |= dp[i - ai]
    ans = inf
    for i in range(k + 1):
        if dp[i]:
            ans = min(ans, max(k - i - i, i - (k - i)))
    if ans:
        print(ans - 1)
    else:
        print(0)

    return


#main
if __name__ == '__main__':
    solve()


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

int main(void) {
    int n;
    cin >> n;
    
    vector<long> a(n);
    for(auto &x: a) cin >> x;

    sort(a.begin(), a.end());

    long am = a[n-1];
    auto lb = lower_bound(a.begin(), a.end()-2, am/2);

    long i = min(am - *lb, *lb);
    
    long j = -1;
    if(lb != a.begin())
        j = min(am - *(lb-1), *(lb-1));

    long an = i < j ? *(lb-1) : *lb;

    cout << am << ' ' << an << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX 514
#define INF (1e9)
 
struct Edge{
    int to,cost,c;
    Edge(int to,int cost,int c) :
        to(to),cost(cost),c(c) {}
};
 
int main(){
    int M,D,N,K;
    int d[MAX][1<<6];    
    while(cin >> M >> N >> K >> D, M){
        vector<Edge> G[MAX];
        vector<int> cake(M);
        for(int i = 0 ; i < M ; i++){
            cin >> cake[i];
        }
        int idx = 0,c;
        string a,b;
        map<string,int> mp;
        for(int i = 0 ; i < D ; i++){
            cin >> a >> b >> c;
            if(!mp.count(a)) mp[a] = idx++;
            if(!mp.count(b)) mp[b] = idx++;
            if(a[0] == 'C'){
                G[mp[b]].push_back(Edge(mp[a],c,a[1]-'1'));             
            }else{
                G[mp[b]].push_back(Edge(mp[a],c,-1));           
            }
            if(b[0] == 'C'){
                G[mp[a]].push_back(Edge(mp[b],c,b[1]-'1'));
            }else{
                G[mp[a]].push_back(Edge(mp[b],c,-1));           
            }
 
        }
        int s = mp["H"],t = mp["D"];
        for(int i = 0 ; i < MAX ; i++){
            for(int j = 0 ; j < (1<<6) ; j++){
                d[i][j] = INF;
            }
        }
        d[s][0] = 0;
        bool update = 1;
        while(update){
            update = 0;
            for(int i = 0 ; i < (int)mp.size() ; i++){
                for(int j = 0 ; j < (int)G[i].size() ; j++){
                    Edge e = G[i][j];
                    for(int S = (1<<6)-1 ; S >= 0 ; S--){
                        int ncost = d[i][S];
                        if(ncost == INF) continue;
                        ncost += e.cost*K;
                        if(e.c == -1){
                            if(ncost < d[e.to][S]){
                                d[e.to][S] = ncost;
                                update = 1;
                            }
                        }else{
                            if(S >> e.c & 1) continue;
                            if(ncost-cake[e.c] < d[e.to][S|(1<<e.c)]){
                                d[e.to][S|(1<<e.c)] = ncost-cake[e.c];
                                update = 1;
                            }
                        }
                    }
                }
            }
        }
        int res = INF;
        for(int i = 0 ; i < (1<<6) ; i++){
            res = min(res, d[t][i]);
        }
        cout << res << endl;
    }
    return 0;
}

Measured memory_bytes: 3296
//Nihal Mittal - nihal_47
//Strike First , Strike Hard , No Mercy !!

/**⠀⠀⠀⠀⠀⠀⣀⣤⣤⣄⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⣰⣿⣿⣿⣿⠿⠿⣿⣿⣿⣿⣿⣿⣿⣧⢀⠀⠀⠀⠀
⠀⠀⠀⣿⣿⣿⠋⠀⠀⠀⠀⠀⠙⠀⠙⣿⣿⣿⣷⢳⢀⠀⠀⠀
⠀⠀⣠⣿⣿⣿⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⢀
⠀⠀⣸⣿⣿⣿⠸⠀⠀⠀⠒⠒⠒⠐⠀⠀⢿⣿⣿⣿⣿⣿⠀⠀
⠀⣴⣿⣿⣿⡿⠀⠒⣋⣙⡒⢰⠀⠤⣖⠒⢾⣿⣿⣿⣿⣧⠀⠀
⢺⣿⣿⣿⣿⢀⠀⠀⠉⠉⠉⠸⠀⡇⠉⠉⠀⢿⣿⣿⣿⣄⠀⠀
⠀⠙⣿⣿⣧⢻⠀⠀⠀⠀⠀⠠⠀⠰⠀⠀⠀⣸⠸⣿⣿⠿⠰⠀
⠀⠀⠀⠹⣿⣿⣿⣷⠀⡠⠙⣲⣔⣅⢡⣰⣷⣿⣿⣿⣧⠀⠀⠀
⠀⠀⠀⣼⣿⣿⣿⣿⠀⡿⠭⠭⠭⠭⢿⠀⣿⢻⣿⣿⠃⠀⠀⠀
⠀⠀⠀⠙⠛⣿⢻⠹⣿⠐⠙⠛⠟⠉⢀⣴⡟⢿⣿⡏⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⡟⠀⠀⠻⣦⣤⣶⠾⠋⠀⠀⠁⡦⢄⢀⠀⠀⠀
⠀⠀⠀⠀⡠⠁⡇⠑⢄⠀⠀⠀⠀⠀⠀⠔⠀⠀⠁⠀⠀⠀⠉⠁
⠀⠔⠊⠁⠀⠀⣇⠀⠀⠀⠑⡤⠤⢎⠁⠀⠀⡘⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢢⠠⠀⡠⢆⠀⠀⡠⠙⢄⠀⡸⠀
**/
#include<bits/stdc++.h>
#define ll long long
#define l long
#define mk make_pair
#define pb push_back
#define in insert
#define se second
#define fi first
#define mod 1000000007
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define all(v) (v).begin(),(v).end()
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
#define pii pair<int,int>
#define maxn 100005
using namespace std;
vector<pii> v[100005];
signed main()
{
    fast;
    
    int n,i;
    cin>>n;
    int deg = 0;
    for(i=0;i<n-1;i++)
    {
    	int x,y;
    	cin>>x>>y;
    	v[x].pb({y,i+1});
    	v[y].pb({x,i+1});
    }
    for(i=1;i<=n;i++)
    {
    	int si = v[i].size();
    	deg = max(deg,si);
    }
    bool vi[n+2] = {false};
    int ans[n+2] = {0};
    int par[n+2] = {0};
    vi[1] = true;
    stack<int> s;
    s.push(1);
    int cn=1;
    while(!s.empty())
    {
    	int st = s.top();
    	s.pop();
    	cn = par[st] + 1;
    	if(cn>deg) cn = 1;
    	for(auto u: v[st])
    	{
    		if(!vi[u.fi])
    		{
    			vi[u.fi] = true;
    			ans[u.se] = cn;
    			par[u.fi] = max(par[u.fi],cn);
    			cn++;
    			if(cn>deg) cn = 1;
    			s.push(u.fi);
    		}
    	}
    }
    cout<<deg<<"\n";
    for(i=1;i<=n-1;i++) cout<<ans[i]<<"\n";
}

Measured memory_bytes: 7424
#include <bits/stdc++.h>
using namespace std;
int main() {
    int s; cin >> s;
    int a = s / 100;
    int b = s % 100;
    bool aa, bb;
    if (0 < a && a <= 12) aa = true;
    else aa = false;
    if (0 < b && b <= 12) bb = true;
    else bb = false;
    if (aa && !bb) cout << "MMYY" << endl;
    else if (!aa && bb) cout << "YYMM" << endl;
    else if (aa && bb) cout << "AMBIGUOUS" << endl;
    else cout << "NA" << endl;
    return 0;
}

Measured memory_bytes: 256
N, K = [int(x) for x in input().split(' ')]
A = [int(x) for x in input().split(' ')]

for i in range(K, N): # [K, N - 1] 0 indexed => [K + 1, N] 1 indexed
  if A[i - K] < A[i]:
    print("Yes")
  else:
    print("No")

Measured memory_bytes: 31748
# -*- coding: utf-8 -*-

N, Q = map(int, input().split())
S = input()

Sl = [0]
for i in range(N):
    Sl.append(Sl[-1] + 1 if S[i:i + 2] == "AC" else Sl[-1])

for _ in range(Q):
    l, r = map(int, input().split())
    print(Sl[r - 1] - Sl[l - 1])


Measured memory_bytes: 6100