akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PI 3.141592653589793
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n, k) for (int i = (n); i >= (k); i--);
#define all(x) (x).begin(), (x).end()
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<class T>vector<T> make_vector(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto make_vector(size_t a, Ts... ts){return vector<decltype(make_vector<T>(ts...))>(a, make_vector<T>(ts...));}
int mod = 1e9 + 7;

signed main() {
    string S;
    cin >> S;
    int ans = 0;
    for (int i = 0; i < S.length() / 2 + (S.length() % 2 == 1); i++) {
        if (S[i] != S[S.length() - i - 1]) ++ans;
    }
    cout << ans << endl;
}



Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {
    private static FastScanner sc = new FastScanner();
    private static boolean DEBUG_FLG = false;

    public static void main(String[] args) {
    	int N = sc.nextInt();
    	System.out.println(180 * (N-2));
    }

    static void debug(long... args) {
    	if(!DEBUG_FLG) return;
    	boolean flg = false;
    	for(long s : args) {
    		if(flg) System.out.print(" ");
    		flg = true;
    		System.out.print(s);
    	}
    	System.out.println();
    }

    static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;
        private boolean hasNextByte() {
            if(ptr < buflen) {
                return true;
            } else {
                ptr = 0;
                try {
                    buflen = in.read(buffer);
                } catch(IOException e) {
                    e.printStackTrace();
                }
                if(buflen <= 0) {
                    return false;
                }
            }
            return true;
        }
        private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
        private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
        private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
        public boolean hasNext() { skipUnprintable(); return hasNextByte();}
        public String next() {
            if (!hasNext()) throw new NoSuchElementException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while(isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
        public int nextInt(){
            return Integer.parseInt(next());
        }
        public double nextDouble(){
            return Double.parseDouble(next());
        }
    }
}


Measured memory_bytes: 23380
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef long long LL;
typedef unsigned long long ULL;
const LL LINF = 0x3f3f3f3f3f3f3f3f; 
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
const int mod = 1e9+7;
const ULL P = 131;
const int N = 2e5+7;

struct node{
	int c;
	int le[15];
}a[15];
int n,m,k;
int ans=INF;

int dis[15];

void dfs(int x,int cost)
{
	int flag=1;
	for(int i=1;i<=m;i++) if(dis[i]<k) flag=0;
	if(flag){
		ans = min(ans,cost); return ;
	}
	if(x>n) return ;
	for(int i=1;i<=m;i++) dis[i] += a[x].le[i];
	dfs(x+1,cost+a[x].c);
	for(int i=1;i<=m;i++) dis[i] -= a[x].le[i];
	
	dfs(x+1,cost);
}

int main()
{
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i].c;
		for(int j=1;j<=m;j++) cin>>a[i].le[j];
	}
	
	dfs(1,0);
	if(ans==INF) cout<<"-1\n";
	else cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3624
#include <iostream>
#define P 1000000007
using namespace std;
typedef long long ll;
int mod_power(ll,int);

int main(){
  int m,n;
  cin>>m>>n;
  cout<<mod_power((ll)m,n)<<endl;
  return 0;
}

int mod_power(ll x,int y){
  ll res=1;
  for(int i=0;i<=30;i++){
    if(y&(1<<i)) res=res*x%P;
    x=x*x%P;
  }
  return res%P;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int f(ll a,ll b){
  if(b==0){return 1;}
  if(b%2==0){return (f(a*a%2019,b/2));}
  if(b%2==1){return (a*f(a,b-1)%2019);}
}
int main() {
  string s;
  cin>>s;
  ll N=s.size();
  ll ans=0;
  vector<ll> sum(N+1);
  sum.at(0)=0;
  for(ll i=1;i<=N;i++){
    sum.at(i)=(sum.at(i-1)+f(10,i-1)*(int)(s.at(N-i)-'0'));
    sum.at(i)%=2019;
  }
  vector<ll> vec(2019);
  for(ll i=0;i<=N;i++){
    vec.at(sum.at(i))++;
  }
  for(ll i=0;i<2019;i++){
    if(vec.at(i)>=2){
      ans+=vec.at(i)*(vec.at(i)-1)/2;
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 5228
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
a = LIST()
b = LIST()

a_cnt = 0
b_cnt = 0

for i in range(N):
	if a[i] < b[i]:
		a_cnt += -(a[i]-b[i])//2
	elif a[i] > b[i]:
		b_cnt += a[i]-b[i]


if b_cnt <= a_cnt:
	print("Yes")
else:
	print("No")
	


Measured memory_bytes: 11884
#include <iostream>
#include <vector>
#include <set>

using namespace std;

class range {
private:
  struct Iterator {
    int val;
    int operator*() {return val;}
    bool operator!=(Iterator& itr) {return val < itr.val;}
    void operator++() {++val;}
  };
  Iterator i, n;
public:
  range(int n) : i({0}), n({n}) {}
  range(int i, int n) : i({i}), n({n}) {}
  Iterator& begin() {return i;}
  Iterator& end() {return n;}
};

template<class T> inline T at(const vector<T> &v, int i) {return v[(i % (int)v.size() + v.size()) % v.size()];}

template<class T> inline bool is_max(T &a, const T &b) {return a < b ? a = b, true : false;}
template<class T> inline bool is_min(T &a, const T &b) {return a > b ? a = b, true : false;}

int main() {
  int t = 0;
  while (true) {
    int n;
    cin >> n;
    if (n == 0) break;
    if (t > 0) cout << endl;
    vector<vector<string>> box(5, vector<string>(5));
    for (int i : range(5)) for (int j : range(5)) cin >> box[i][j];
    int m1, m2;
    cin >> m1;
    set<int> a;
    for (int _ : range(m1)) {
      int aa;
      cin >> aa;
      a.insert(aa);
    }
    cin >> m2;
    set<int> b;
    for (int _ : range(m2)) {
      int bb;
      cin >> bb;
      b.insert(bb + 1);
    }
    for (int _ : range(n)) {
      vector<vector<string>> next = box;
      for (int i : range(5)) for (int j : range(5)) for (int k : range(5)) {
        if (box[i][j][k] == '0') {
          int cnt = 0;
          for (int ii : range(-1, 2)) for (int jj : range(-1, 2)) for (int kk : range(-1, 2)) {
            if (i + ii < 0 || 5 <= i + ii) continue;
            if (j + jj < 0 || 5 <= j + jj) continue;
            if (k + kk < 0 || 5 <= k + kk) continue;
            if (box[i + ii][j + jj][k + kk] == '1') ++cnt;
          }
          if (a.count(cnt)) next[i][j][k] = '1';
        } else {
          int cnt = 0;
          for (int ii : range(-1, 2)) for (int jj : range(-1, 2)) for (int kk : range(-1, 2)) {
            if (i + ii < 0 || 5 <= i + ii) continue;
            if (j + jj < 0 || 5 <= j + jj) continue;
            if (k + kk < 0 || 5 <= k + kk) continue;
            if (box[i + ii][j + jj][k + kk] == '1') ++cnt;
          }
          if (!b.count(cnt)) next[i][j][k] = '0';
        }
      }
      box = next;
    }
    cout << "Case " << ++t << ":" << endl;
    for (int i : range(5)) {
      for (int j : range(5)) cout << box[i][j] << endl;
      if (i != 4) cout << endl;
    }
  }
}

Measured memory_bytes: 1224
#include <bits/stdc++.h>
#define N 500005
using namespace std;
typedef long long ll;
const int mod1=1e9+7,mod2=1e9+9,C=200017;
int n;
ll bin[2][N],a[N];
char s[N];
map<pair<ll,ll>,int> mp;
pair<ll,ll> g[N];
ll quick_pow(ll a,ll b,const ll mod){
	ll ans=1;
	for(;b;b>>=1,a=a*a%mod)
		if(b&1) ans=ans*a%mod;
	return ans;
}
int main(){
	scanf("%d",&n);
	scanf("%s",s+1);
	bin[0][0]=bin[1][0]=1;
	for(int i=1;i<=n+n;i++){
		bin[0][i]=bin[0][i-1]*C%mod1;
		bin[1][i]=bin[1][i-1]*C%mod2;
	}
	ll now1=0,now2=0;
	pair<ll,ll> w;
	for(int i=1,pos=n;i<=n;i++){
		if(s[i]=='<') pos--;
		if(s[i]=='>') pos++;
		if(s[i]=='-'){
			a[pos]--;
			now1=(now1-bin[0][pos])%mod1;
			now2=(now2-bin[1][pos])%mod2;
		}
		if(s[i]=='+'){
			a[pos]++;
			now1=(now1+bin[0][pos])%mod1;
			now2=(now2+bin[1][pos])%mod2;
		}
		now1=(now1+mod1)%mod1;
		now2=(now2+mod2)%mod2;
		w=make_pair(now1,now2);
		g[i]=w;
		if(mp.find(w)==mp.end()) mp[w]=0;
		mp[w]++;
	}
	ll ans=mp[w];
	ll inv1=quick_pow(C,mod1-2,mod1),inv2=quick_pow(C,mod2-2,mod2);
	ll w1=1,w2=1,add1=0,add2=0;
	for(int i=1;i<n;i++){
		if(s[i]=='<'){
			w1=w1*inv1%mod1;
			w2=w2*inv2%mod2;
			//add1=add1%mod1;
			//add2=add2*inv2%mod2;
		}
		if(s[i]=='>'){
			w1=w1*C%mod1;
			w2=w2*C%mod2;
			//add1=add1*C%mod1;
			//add2=add2*C%mod2;
		}
		if(s[i]=='+'){
			add1=(add1+bin[0][n]*w1)%mod1;
			add2=(add2+bin[1][n]*w2)%mod2;
		}
		if(s[i]=='-'){
			add1=(add1-bin[0][n]*w1)%mod1;
			add2=(add2-bin[1][n]*w2)%mod2;
		}
		w.first=(g[n].first*w1+add1)%mod1;
		w.second=(g[n].second*w2+add2)%mod2;
		w.first=(w.first+mod1)%mod1;
		w.second=(w.second+mod2)%mod2;
		mp[g[i]]--;
		if(mp.find(w)!=mp.end()) ans+=mp[w];
	}
	printf("%lld\n",ans);
	return 0;
}

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

int main()
{
    int h,m,s;

    int xs;

    cin >> xs;

    h = xs / 3600;
    m = (xs % 3600) / 60;
    s = (xs % 3600) % 60;

    cout << h << ':' << m << ':' << s << endl;

    return 0;
}


Measured memory_bytes: 3084
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>
#include <numeric>

using namespace std;

#define mod 1000000007


int main()
{
	int x, a, b;
	cin >> x >> a >> b;
	cout << (x - a) % b << endl;
}



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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

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

signed main(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    a+=b;c+=d;

    if(a<c)cout<<"Right"<<endl;
    else if(a>c)cout<<"Left"<<endl;
    else cout<<"Balanced"<<endl;
    return 0;
}


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

using namespace std;

using ll= long long;

#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define _set(x) __builtin_popcount(x)
#define PI  3.14159265358979323846264338327950L
#define double long double
void solve(){
    double a,b,h,m;
    cin>>a>>b>>h>>m;
    double mx= b*sin(2*PI*m/60);
    double my= b*cos(2*PI*m/60);
    double hx= a*sin(2*PI*((h +m/60.0L)/12.0L));
    double hy= a*cos(2*PI*((h +m/60.0L)/12.0L));
    cout<<fixed<<setprecision(16);
    // cout<<mx<<" "<<my<<" "<<hx<<" "<<hy<<endl;
    cout<<sqrtl((hx-mx)*(hx-mx) + (hy-my)*(hy-my))<<"\n";
}

int32_t main(){
	IOS
	// freopen("input.txt","r",stdin);
	int _;
	// cin>>_;
	_=1;
	while(_--){
        solve();
    }
	return 0;
}

/*
   check for overflows int long long
   correct size of array
*/

Measured memory_bytes: 4192
// 失敗するからこそ そこから立ち向かって行く強さがあってそんな強さが本当の強さだと私は思うから
#ifdef DAIJOBU
#include "/home/v-o_o-v/deb.h"
#define deb(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#include <bits/stdc++.h>
#define deb(x...)
#endif 

using namespace std;

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

	int max_cnt = 0;
	map<string, int> m;
	string s;
	string t;
	while(cin >> s){
		m[s]++;
		if(t.size() < s.size())t = s;
		max_cnt = max(max_cnt, m[s]);
	}
	for(auto i:m){
		if(i.second == max_cnt)s = i.first;
	}
	cout << s << ' ' << t << '\n';
	return 0;
}


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

using namespace std;

class Solution {
public:
	void solve() {
		int n;
		cin >> n;
		vector<int> a(n, 0);
		for (int i = 0; i < n; i++) cin >> a[i];
		unordered_map<int, int> cnt;
		long long ans = 0;
		for (int i = 0; i < n; i++) {
			ans += cnt[i - a[i]];
			cnt[a[i] + i]++;
		}
		cout << ans << "\n";

		return;
	};
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	Solution solution;
	solution.solve();
	return 0;
}

Measured memory_bytes: 19220
#include <iostream>
using namespace std;
int main(){
    int h, n, a, sum, i;
    cin >>h>>n;
    for(i=0;n>i;i++){
        cin>>a;
        sum+=a;
    }
    if(h<=sum){
        cout<<"Yes";
    }
    else{
        cout<<"No";
    }
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int gcd(int a, int b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

int main() {
    int n, x;
    vector<int> a, b;

    scanf("%d%d", &n, &x);
    a.push_back(x);
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        a.push_back(x);
    }

    sort(a.begin(), a.end());
    int ans = a[1] - a[0];
    for (int i = 2; i < a.size(); i++) {
        ans = gcd(ans, a[i] - a[i-1]);
    }
    printf("%d\n", ans);

    return 0;
}


Measured memory_bytes: 892
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int r = sc.nextInt();
		int D = sc.nextInt();
		int x_2000 = sc.nextInt();
		
		int prev = x_2000;
		for(int i=0; i<11; i++) {
			if(i==0) {
				continue;
			} else {
				int next = r * prev - D;
				System.out.println(next);
				prev = next;
			}
		}
		
	}

}


Measured memory_bytes: 21204
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,ac=0,tle=0,wa=0,re=0;
    string s;
    cin>>n;
    while(n--)
    {
        cin>>s;
        if(s=="AC")
            ac++;
        else if(s=="TLE")
            tle++;
        else if(s=="WA")
            wa++;
        else
            re++;
    }
    cout<<"AC x "<<ac<<endl<<"WA x "<<wa<<endl<<"TLE x "<<tle<<endl<<"RE x "<<re<<endl;

    return 0;
}


Measured memory_bytes: 3620
#include<stdio.h>
#include<iostream>
#include<cassert>
#include<stack>
#include<algorithm>
#define MAX 505
#define BLOCK 0

using namespace std;

struct Rectangle{ int height;  int pos; };

int getLargestRectangle( int size, int buffer[]){
    stack<Rectangle> S;
    int maxv = 0;
    buffer[size] = 0;
    
    for ( int i = 0; i <= size; i++ ){
        Rectangle rect;
        rect.height = buffer[i];
        rect.pos = i;
        if ( S.empty() ){
            S.push( rect );
        } else {
            if ( S.top().height < rect.height ){
                S.push( rect );
            } else if ( S.top().height > rect.height ) {
                 int target = i;
                 while ( !S.empty() && S.top().height >= rect.height){
                     Rectangle pre = S.top(); S.pop();
                     int area = pre.height * (i - pre.pos);
                     maxv = max( maxv, area);
                     target = pre.pos;
                 }
                 rect.pos = target;
                 S.push(rect);
             }
         }
     }
     return maxv;
 }

int H, W;
int buffer[MAX][MAX];
int T[MAX][MAX];
 
int getLargestRectangle(){
    for ( int i = 0; i < H; i++ ){
	for ( int j = 0; j < W; j++ ){
	    T[i][j] = 0;
	}
    }
     
    for ( int j = 0; j < W; j++ ){
	int sequence = 0;
	for ( int i = 0; i < H; i++ ){
	    if ( buffer[i][j] == BLOCK ){
		sequence = T[i][j] = 0;
	    } else {
		T[i][j] = ++sequence;
	    }
	}
    }
    
    int maxv = 0;
    for ( int i = 0; i < H; i++ ){
	maxv = max( maxv, getLargestRectangle( W, T[i] ) );
    }
    
    return maxv;
}

int main(void){
    char ch;
    while(1){
	scanf("%d %d", &H, &W);
	if ( H == 0 && W == 0) break;
	scanf("%c", &ch);
	char ch;
	for ( int i = 0; i < H; i++ ){
	    for ( int j = 0; j < W; j++ ){
		scanf("%c", &ch);
		if ( ch == '*' ) buffer[i][j] = 0;
		else buffer[i][j] = 1;
	    }
	    scanf("%c", &ch);
	}
	cout << getLargestRectangle() << endl;
    }
    
    return 0;
}

Measured memory_bytes: 2920
#include <stdio.h>
#define MAX_N 100

int n;
int a[MAX_N];

int main(void){
    
    scanf("%d",&n);
    for(int i = 0; i<n;i++){
        scanf("%d",&a[i]);
    }

    for(int i = 0; i<n;i++){
        int key = a[i];
        int j = i -1;
        while(j >= 0 && a[j] > key){
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = key;

        for(int idx = 0; idx < n-1; idx++){
            printf("%d ",a[idx]);
        }
        printf("%d",a[n-1]);
        printf("\n");
    }
    return 0;
}

Measured memory_bytes: 2680
#include <stdio.h>

int main()
{
    int a[3],d;
    scanf("%d%d%d",&a[0],&a[1],&a[2]);
    for(int i=0;i<3-1;i++)
    {
        for(int j=0;j<3-i-1;j++)
        {
            if(a[j] > a[j+1])
            {
                d = a[j];
                a[j] = a[j+1];
                a[j+1] = d;
            }
        }
    }
    printf("%d %d %d\n",a[0],a[1],a[2]);
}


Measured memory_bytes: 2720
import java.util.Scanner;

public class Main{
	public  static void main(String[] args) {
		Scanner src = new Scanner(System.in);
		int a = src.nextInt();
		int b = src.nextInt();
		 if(a<b) {
			 System.out.println("a < b");
		 }else if(a>b){
			 System.out.println("a > b");
		 }else if(a==b){
			 System.out.println("a == b");
		 }
	}
}



Measured memory_bytes: 26068
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
template<class T> void chmin(T &a,const T &b){if(a>b) a=b;}
template<class T> void chmax(T &a,const T &b){if(a<b) a=b;}

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

  ll H,W;
  cin>>H>>W;

  ll ans=0;
  if(H%2&&W%2) ans+=W*(H/2)+W/2+1;
  else if(W%2) ans+=W*(H/2);
  else if(H%2) ans+=H*(W/2);
  else ans+=W*H/2;

  if(H==1||W==1) cout<<1<<endl;
  else cout<<ans<<endl; 

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <bitset>
#include <vector>
#include <queue>
#include <map>
#include <set>

#define i64 int64_t
#define ff(ii,nn,mm) for(int ii=nn;ii<mm;ii++)
#define st(vvv) sort(vvv.begin(),vvv.end())
#define rvs(vvv) reverse(vvv.begin(),vvv.end())
int inf = 1000000007;

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> data(n);
	ff(i, 0, n) {
		cin >> data.at(i);
	}
	i64 ans = inf;
	ff(i, -100, 101) {
		i64 pre = 0;
		ff(j, 0, n) {
			pre += (data.at(j) - i) * (data.at(j) - i);
		}
		ans = min(ans, pre);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
def main():
    N, K = map(int, input().split())
    h = [0]*N
    for i in range(N):
        h[i] = int(input())
    h.sort()
    
    ans = 10**10
    for i in range(N-K+1):
        ans = min(ans, h[i+K-1]-h[i])
    print(ans)
main()

Measured memory_bytes: 7472
#include<iostream>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define int long long
using namespace std;

signed main(){
	int k,a,b;
	int sum=1;
	cin>>k>>a>>b;
	if(k<a){
		sum+=k;
		k=0;
	}else{
		sum+=(a-1);
		k-=(a-1);
	}
	while(k>0){
		if(b>a&&k>1&&(b-a)>2){
			sum+=k/2*(b-a);
			k%=2;
		}else{
			sum+=k;
			k=0;
		}
	}
	cout<<sum<<endl;
	return 0;
}

Measured memory_bytes: 384
#include<stdio.h>
#include<limits.h>

#define N 101
#define WHITE 0
#define GRAY 1
#define BLACK 2

int Q[N], M[N][N], color[N], d[N], n, f=1, c=1;

void Enqueue(int n){
  Q[f] = n;
  f++;
  if(f == N) f=1;
}

int Dequeue(){
  int x = c;
  c++;
  if(c == N) c=1;
  return Q[x];
}

void BFS(int s){
  int i, u;
  for(i = 1; i <= n; i++){
    color[i] = WHITE;
    d[i] = -1;
  }
  color[s] = GRAY;
  d[s] = 0;
  Enqueue(s);
  while(f != c){
    u = Dequeue();
    for(i = 1; i <= n; i++){
      if(color[i] == WHITE && M[u][i] == 1){
	color[i] = GRAY;
	d[i] = d[u] + 1;
	Enqueue(i);
      }
    }
    color[u] = BLACK;
  }
}

int main(){
  int i, j, k, x, s, m;
  for(i=1; i < n; i++){
    for(j=1; j < n; j++) M[i][j] = 0;
  }
  scanf("%d",&n);
  for(i=1; i <= n; i++){
    scanf("%d%d", &m, &k);
    if(i == 1) s = 1;
    for(j=0; j < k; j++){
      scanf("%d",&x);
      M[m][x] = 1;
    }
  }
  BFS(s);
  for(i=1; i <= n; i++){
    printf("%d %d\n", i, d[i]);
  }
  return 0;
}

Measured memory_bytes: 636
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int mp[1001][1001];

int main(){
	int W;char c;
	for(int num = 0;cin >> W&&W;num++){
		int v[1001], w[1001], n;
		cin >> n;
		fill((int*)mp, (int*)(mp+n+1), 0);
		for(int i = 0;i < n;i++)cin >> v[i] >> c >> w[i];
		for(int i = 0;i < n;i++){
			for(int j = 0;j < W+1;j++){
				if(j < w[i])mp[i+1][j] = mp[i][j];
				else mp[i+1][j] = max(mp[i][j], mp[i][j-w[i]]+v[i]);
			}
		}
		int ans = 0;
		for(int i = 1;i < W+1;i++){
			if(mp[n][i] > mp[n][ans])ans = i;
		}
		cout << "Case " << num+1 << ":" << endl;
		cout << mp[n][ans] << endl << ans << endl;
	}
	return 0;
}
/*
1
y eazqyp pnop pngtg ye obmpngt xmybp mr lygw
*/

Measured memory_bytes: 6996
n = int(input())
a = list(map(int, input().split()))
if n%2:
    for i in range(n//2+1):
        print(str(a[n-1-2*i])+" ", end="")
    for i in range(n//2):
        print(str(a[1+2*i])+" ", end="")
    print()
else:
    for i in range(n//2):
        print(str(a[n-1-2*i])+" ", end="")
    for i in range(n//2):
        print(str(a[2*i])+" ", end="")
    print()




Measured memory_bytes: 26180
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        ArrayList<String> blue = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            blue.add(sc.next());
        }

        int m = sc.nextInt();
        ArrayList<String> red = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            red.add(sc.next());
        }
        sc.close();

        Set<String> ts = new HashSet<>(blue);

        int ans = 0;

        for (String str : ts) {
            int count = 0;
            for (int i = 0; i < n; i++) {
                if (str.equals(blue.get(i))) {
                    count++;
                }
            }
            for (int i = 0; i < m; i++) {
                if (str.equals(red.get(i))) {
                    count--;
                }
            }
            if (ans < count) {
                ans = count;
            }
        }
        System.out.println(ans);
    }
}

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

static int cmpfunc(const void *lhs, const void *rhs)
{
    return strcmp(lhs, rhs);
}

int main ()
{
  int N;
  scanf("%d",&N);
  char S[N][11];


  for (int i = 0;i<N;i++)
  {
  	scanf("%s",S[i]);

  }
qsort(S, N, sizeof(S[0]), cmpfunc);
 int count = 1;
 for (int i = 0;i<N-1;i++)
 {
 	if (strcmp(S[i],S[i+1])!=0)count++;
 }
  printf("%d",count);

 return 0;
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

const ll MOD = ll(1e9 + 7);
const ll LLINF = LLONG_MAX;
const int IINF = 99999999;
const int MAX_N = int(1e5) + 5;
const double EPS = 1e-8;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)


int main() {
    int n, k, a[MAX_N], imin;
    cin >> n >> k;
    REP(i,n){
        cin >> a[i];
        if(a[i]==1)imin = i;
    }
    cout << (n-2)/(k-1) + 1 << endl;
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template<typename T> istream& operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
template<typename T> ostream& operator<<(ostream &os, vector<T> &vec){ os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream& operator<<(ostream &os, set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T1, typename T2> ostream& operator<<(ostream &os, pair<T1, T2> &pa){ os << "(" << pa.first << "," << pa.second << ")"; return os; }
template<typename TK, typename TV> ostream& operator<<(ostream &os, map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;

int N;
vector<double> A, B, C;

// 1-indexed BIT (i : [1, len])
template<typename T, int len>
struct BIT
{
    array<T, len + 1> val;
    void reset() { val.fill(0); }
    BIT() { reset(); }
    void add(int pos, T v)
    {
        while (pos > 0 && pos <= len)
        {
            val[pos] += v;
            pos += pos & -pos;
        }
    }
    T sum(int pos)
    {
        T res = 0;
        while (pos > 0)
        {
            res += val[pos];
            pos -= pos & -pos;
        }
        return res;
    }
};

BIT<int, 40002> bit;
int count_inversion(const vector<int> &vec)
{
    bit.reset();
    int ans = 0;
    for (auto v : vec)
    {
        ans += bit.sum(v);
        bit.add(v + 1, 1);
    }
    return ans;
}

double solve(const vector<double> &A, const vector<double> &B, const vector<double> &C)
{
    using p = pair<double, double>;
    vector<p> info(N);
    REP(i, N) info[i] = p((double)A[i] / B[i], (double)C[i] / B[i]);
    sort(info.begin(), info.end());

    double l = -2E8, r = 2E8;
    while (r - l > 1E-10 and (r - l) > (abs(l) + abs(r)) * 1E-10)
    {
        double c = (l + r) / 2;
        vector<pair<double, int>> vec(N);
        REP(i, N) vec[i] = make_pair(info[i].second - info[i].first * c, i + 1);
        sort(vec.begin(), vec.end());
        vector<int> vec2(N);
        REP(i, N) vec2[i] = vec[i].second;
        if (count_inversion(vec2) > N * (N - 1) / 2 / 2) l = c;
        else r = c;
    }
    return l;
}

int main()
{
    cin >> N;
    A.resize(N);
    B.resize(N);
    C.resize(N);
    REP(i, N) cin >> A[i] >> B[i] >> C[i];

    cout << solve(A, B, C) << " " << solve(B, A, C) << endl;
}


Measured memory_bytes: 2816
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<ll>; using VVI = vector<VI>; using VVVI = vector<VVI>;
const int inf=1e9+7;
const ll INF=1LL<<58;
const ll mod=1e9+7;

int main(){
  int i,j;
  ll a[100];
  for(i=0;i<100;i++) a[i]=0;
  for(i=1;i<=9;i++){
    for(j=1;j<=9;j++){
      a[i*j]=1;
    }
  }
  int n;
  cin>>n;
  if(a[n]==1) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <math.h>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long ll;

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

int main() {

    ll N;
    cin >> N;
    ll out = N;
    string S[N];
    rep(i,N) cin >> S[i];
    sort(S,S+N);
    rep(i,N){
        if(S[i]==S[i+1]) out--;
    }
    cout << out << endl;
    return 0;
}


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

struct Edge {
  int to;
  int weight;
};

vector<vector<Edge>> tree;
vector<ll> cost;

void dfs(int v, int par, ll dist)
{
  cost[v] = dist;

  for (auto p : tree[v]) {
    if (p.to == par) continue;
    dfs(p.to, v, dist + p.weight);
  }
}

int main()
{
  int N, a, b, c, Q, K, x, y;
  cin >> N;
  tree.resize(N);
  cost.resize(N);
  rep(i, N-1) {
    cin >> a >> b >> c;
    a--; b--;
    tree[a].push_back({b, c});
    tree[b].push_back({a, c});
  }

  cin >> Q >> K;
  dfs(--K, -1, 0);
  rep(i, Q) {
    cin >> x >> y;
    x--;  y--;
    cout << cost[x] + cost[y] << endl;
  }

  return 0;
}

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

bool check = true;

int main(){
    int n,m;
    cin >> n >> m;
    char a[50][50],b[50][50];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
        cin >> a[i][j];
    }
    for(int i=0;i<m;i++){
        for(int j=0;j<m;j++)
        cin >> b[i][j];
    }
    
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            check = true;
            for(int k=0;k<m;k++){
                for(int l=0;l<m;l++){
                    if(a[i+k][j+l]!=b[k][l])check = false;
                }
            }
            if(check==true){cout << "Yes" << endl;return 0;}
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<string>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

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

	map<ll, ll> A;
	rep(i, N)
	{
		ll tmp;
		cin >> tmp;
		A[tmp]++;
	}

	map<ll, ll> B;
	rep(i, N)
	{
		ll tmp;
		cin >> tmp;
		B[tmp]++;
	}

	map<ll, ll> C;
	rep(i, N)
	{
		ll tmp;
		cin >> tmp;
		C[tmp]++;
	}

	map<ll, ll> sumC;
	sumC[C.rbegin()->first] = C.rbegin()->second;

	for (auto iter = next(C.rbegin()); iter != C.rend(); ++iter)
	{
		sumC[iter->first] = sumC[prev(iter)->first] + iter->second;
	}

	map<ll, ll> countB;

	//B[i]より大きいCの要素の個数を数える。
	for(auto b : B)
	{
		countB[b.first] = 0;

		auto iter = sumC.upper_bound(b.first);

		if (iter != sumC.end()) countB[b.first] = b.second * iter->second;
	}

	//countBの累積和
	map<ll, ll> sumB;
	sumB[countB.rbegin()->first] = countB.rbegin()->second;

	for (auto iter = next(countB.rbegin()); iter != countB.rend(); ++iter)
	{
		sumB[iter->first] = sumB[prev(iter)->first] + iter->second;
	}

	ll ans = 0;

	for (auto a : A)
	{
		auto iter = sumB.upper_bound(a.first);

		if(iter != sumB.end()) ans += a.second * iter->second;
	}

	cout << ans << endl;

	return 0;
}

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

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

int main(){
    int N;
    cin >> N;
    vector<string> s(N);
    rep(i, N) cin >> s[i];
    int ans = 0;

    //文字列の先頭が'B'で、末尾が'A'の文字列の個数
    int cnt_AB = 0;
    //文字列の末尾が'A'の文字列の個数
    int cnt_A = 0;
    //文字列の先頭が'B'の文字列の個数
    int cnt_B = 0;

    //いろいろな数え上げを行う
    rep(i, N){
        //各文字列内に含まれる'AB'の個数を数える
        string t = s[i];
        int len = (int)t.size();
        rep(j, len-1){
            if(t[j] == 'A' && t[j+1] == 'B') ans++;
        }

        //文字列の末尾、先頭に注目する
        if(t[0] == 'B' && t[len-1] == 'A') cnt_AB++;
        else if(t[0] == 'B') cnt_B++;
        else if(t[len-1] == 'A') cnt_A++;
    }

    if(cnt_A != 0 || cnt_B != 0){
        ans += min(cnt_A + cnt_AB, cnt_B + cnt_AB);
    }else{
        if(cnt_AB > 1) ans += (cnt_AB-1);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3728
#include<iostream>
#include<vector>
#define lli long long int
#include<climits>
#define pb push_back
using namespace std;


int main()
{
    
    int h,w,i,j;
    cin>>h>>w;
    
    vector<vector<int>>dp1(h+1,vector<int>(w+1));
    vector<vector<int>>dp2(h+1,vector<int>(w+1));
    vector<vector<int>>dp3(h+1,vector<int>(w+1));
    
    for(i=1;i<=h;i++)
        for(j=1;j<=w;j++)
            cin>>dp1[i][j];
    
    for(i=1;i<=h;i++)
        for(j=1;j<=w;j++)
            cin>>dp2[i][j];
    
    for(i=1;i<=h;i++)
        for(j=1;j<=w;j++)
            dp3[i][j] = abs(dp1[i][j]-dp2[i][j]);
    
    vector<vector<vector<int>>>dp(h+1,vector<vector<int>>(w+1,vector<int>(12801,0)));
    
    dp[h][w][abs(dp3[h][w])] = 1;
    
    for(i=h,j=w-1;j>=1;j--)
        for(int k=0;k<=6400;k++)
            if(dp[i][j+1][k]==1)
            {
                dp[i][j][abs(k+dp3[i][j])] = 1;
                dp[i][j][abs(k-dp3[i][j])] = 1;
            }
    
    for(i=h-1;i>=1;i--)
    {
        for(j=w;j>=1;j--)
        {
            if(j==w)
            {
                for(int k=0;k<=6400;k++)
                    if(dp[i+1][j][k]==1)
                    {
                        dp[i][j][abs(k+dp3[i][j])] = 1;
                        dp[i][j][abs(k-dp3[i][j])] = 1;
                    }
            }
            
            else
            {
                for(int k=0;k<=6400;k++)
                {
                    if(dp[i+1][j][k]==1)
                    {
                        dp[i][j][abs(k+dp3[i][j])] = 1;
                        dp[i][j][abs(k-dp3[i][j])] = 1;
                    }
                    if(dp[i][j+1][k]==1)
                    {
                        dp[i][j][abs(k+dp3[i][j])] = 1;
                        dp[i][j][abs(k-dp3[i][j])] = 1;
                    }
                }
            
            }
        }
    }
    
    
    int mymin = INT_MAX;
    for(int k=0;k<=6400;k++)
    {
        if(dp[1][1][k]==1) mymin = min(k,mymin);
        
    }
    cout<<mymin<<endl;
    
    
    
}



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

int main()
{
 
	int n, a = 0, w = 0, t = 0, r = 0;
	cin >> n;
	while (n--)
	{
		string s;
		cin >> s;
		if (s == "AC")
			a++;
		else if (s == "TLE")
			t++;
		else if (s == "WA")
			w++;
		else
			r++;
	}
	cout << "AC " << "x " << a << "\n";
	cout << "WA " << "x " << w << "\n";
	cout << "TLE " << "x " << t << "\n";
	cout << "RE " << "x " << r << "\n";
}

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

int main()
{
	int a,b;
	char op;
	scanf("%d %c %d",&a,&op,&b);
	//cout<<b<<endl;
	if(op=='+')
	{
		cout<<a+b<<endl;
	}
	else
	{
		cout<<a-b<<endl;
	}
	
}

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

typedef long long ll;

ll a[200001];
ll b[200001];

int main(){
    ll n; cin >> n;
    for(ll i=1;i<=n;i++){
        cin >> a[i];
        b[a[i]]++;
    }
    ll ans=0;
    for(ll i=1;i<=n;i++) ans+=b[i]*(b[i]-1)/2;
    for(ll i=1;i<=n;i++){
        cout << ans+(b[a[i]]-1)*(b[a[i]]-2)/2-b[a[i]]*(b[a[i]]-1)/2 << endl;
    }
}

Measured memory_bytes: 4736
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
using loop = int;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i,a,n) for(loop (i)=(a);(i)<(n);++(i))
#define eFOR(i,a,n) for(loop (i)=(a);(i)<=(n);++(i))
#define rFOR(i,a,n) for(loop (i)=(n)-1;(i)>=(a);--(i))
#define erFOR(i,a,n) for(loop (i)=(n);(i)>=(a);--(i))
#define each(i, a) for(auto &i : a)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
#define out(y,x) ((y) < 0 || h <= (y) || (x) < 0 || w <= (x))
#define line cout << "------------------------\n" 
#define ENDL(i,n) ((i) == (n) - 1 ? "\n" : " ")
#define stop system("pause") //comment out this on AOJ.
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10;
constexpr ld pi = 3.1415926535897932;
template<class T>inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; }return false; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }

int main() {
    init();

    int n; ll x; cin >> n >> x;
    VL a(n); cin >> a;
    SORT(a);
    int ans = 0;
    FOR(i, 0, n - 1)if (a[i] <= x) {
        x -= a[i];
        ++ans;
    }
    if (x == a.back())++ans;
    cout << ans << "\n";
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<ll, int> P;
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; }

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<ll> x(m), d(m-1);
	rep(i,m) cin >> x[i];
	sort(x.begin(), x.end());
	rep(i,m-1) d[i] = x[i+1] - x[i];
	sort(d.begin(), d.end());
	ll ans = 0;
	rep(i,min(m-1,max(0,m-n))){
		ans += d[i];
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 4560
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <stdio.h>
#include <vector>
#include <time.h>
#include <iomanip>
#include <thread>
#include <atomic>
#include <mutex>
#include <future>
#define double long double
#define int long long
#define low lower_bound
#define upp upper_bound
#define mod 1000000007 //10^9+7
#define inf 10000000000000000 //10^16
#define rep(i,n) for(int i=0;i<n;i++)
#define all(vec) vec.begin(),vec.end()
#define vsort(vec) sort(all(vec))
#define vrever(vec) reverse(all(vec));
#define vunsort(vec) vsort(vec); vrever(vec);
#define bisea binary_search
#define cend cout<<endl;
#define P pair<int,int>
#define prique priority_queue<P,vector<P>,greater<P>>
using namespace std;
struct edge { int to, cost; };
int n, q, k;
vector<edge>g[114514];
int d[114514];
void dijkstra(int s) {
	prique que;
	rep(i, n) d[i] = inf;
	d[s] = 0;
	que.push(P(0, s));
	while (que.size()) {
		P p = que.top(); que.pop();
		int v = p.second;
		if (d[v] < p.first) continue;
		rep(i, g[v].size()) {
			edge e = g[v][i];
			if (d[e.to] > d[v] + e.cost) {
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
			}
		}
	}
}
signed main() {
	cin >> n;
	rep(i, n - 1) {
		int a, b, c;
		cin >> a >> b >> c;
		a--;
		b--;
		edge e;
		e.to = b;
		e.cost = c;
		g[a].push_back(e);
		edge w;
		w.to = a;
		w.cost = c;
		g[b].push_back(w);
	}
	cin >> q >> k;
	k--;
	dijkstra(k);
	rep(i, q) {
		int x, y;
		cin >> x >> y;
		x--;
		y--;
		cout << d[x] + d[y] << endl;
	}
}


Measured memory_bytes: 11504
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define int long long
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int power[500005];
int mod=1e9+7;

signed main()
{
     ios_base::sync_with_stdio(false);
     cin.tie(NULL);  
//  #ifndef ONLINE_JUDGE
//     freopen ("INPUT.txt" , "r" , stdin);
//     freopen ("OUTPUT.txt" , "w" , stdout);
//  #endif

// -------------------------------------Code starts here---------------------------------------------------------------------     

   int n;
   cin>>n;
   int c[n];
   for(int i=0;i<n;i++)
   {
      cin>>c[i];
   }
   power[0]=1;
   for(int i=1;i<=500000;i++)
   {
      power[i]=(power[i-1]*2)%mod;
   }
   sort(c,c+n);
   int ans=0;
   for(int i=0;i<n;i++)
   {
      int x1=i;
      int x2=n-x1-1;
      if(x2==0)
      {
         int z=power[x1];
         z=(z*c[i])%mod;
         // z=(z*2)%mod;
         // cout<<z<<"\n";
         ans=(ans+z)%mod;
         continue;
      }
      int z=(power[x1+x2-1])%mod;
      z=(z*(x2+2))%mod;
      z=(z*c[i])%mod;
      ans=(ans+z)%mod;
      // cout<<ans<<"\n";
   }
   // cout<<ans;
   ans=(ans*power[n])%mod;
   cout<<ans;
   
// -------------------------------------Code ends here------------------------------------------------------------------
     clock_t clk;
 	clk = clock();
 
    clk = clock() - clk;
 	cerr << fixed << setprecision(6) << "Time: " << ((double)clk)/CLOCKS_PER_SEC << "\n";
 	return 0;
 }

Measured memory_bytes: 5760
#include <iostream>
#include <bitset>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
using ll = long long int;
using dd = long double;
const ll MOD = 1e9 + 7;

vector<string> dfs(string s, ll depth, vector<char> symbol)
{
    vector<string> ret;
    if (depth == 0)
    {
        ret.push_back(s);
        return ret;
    }

    for (ll i = 0; i < symbol.size(); i++)
    {
        auto vec = dfs(s + symbol[i], depth - 1, symbol);
        for (auto &&e : vec)
        {
            ret.push_back(e);
        }
    }
    return ret;
}

ll gcd(ll a, ll b)
{
    if (a % b == 0)
    {
        return b;
    }
    return gcd(b, a % b);
}

enum Tenki
{
    Sunny,
    Cloudy,
    Rainy
};

int main()
{
    map<ll, ll> mp;
    for (ll i = 0; i < 3; i++)
    {
        ll ai;
        cin >> ai;
        mp[ai] += 1;
    }

    if (mp[5] == 2 && mp[7] == 1)
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
}

Measured memory_bytes: 256
// Sharing Cookies

#include <iostream>

using namespace std;

int main(){
	int A, B;
	cin >> A >> B;

	if (A % 3 == 0 || B % 3 == 0 || (A+B) % 3 == 0)
		cout << "Possible" << endl;
	else
		cout << "Impossible" << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <string>
#include <string.h>
#include <cstdlib>
#include <iomanip>
#include <stdio.h>

using namespace std;


int main(){

  int n,s[1000];
  double m,a2;
  while(1){
    scanf("%d\n",&n);
    if(n==0)
      return 0;
    m=0;
    a2=0;
    for(int i=0;i<n;i++){
      scanf("%d",&s[i]);
      m+=s[i];
    }
    m/=n;
    for(int i=0;i<n;i++){
      a2+=pow(s[i]-m,2);
    }
    printf("%.8lf\n",sqrt(a2/n));
  }
}


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

int n,k,arr[105],mini;
bool dp[100005];

int main(){
	scanf("%d%d",&n,&k);
	mini = 1000000000;
	for (int i =0 ; i<n;i++){
		scanf("%d",&arr[i]);
		mini = min(mini,arr[i]);
	}
	for (int i =0; i<=k;i++){
		if(i<mini){
			dp[i] = 1;
		} else{
			bool bisa = false;
			for (int j = 0;j<n;j++){
				if(i-arr[j]>=0 && dp[i-arr[j]]==1) bisa = true;
			}
			if(bisa) dp[i] = 0;
			else dp[i] = 1;
		}
	}
	if(dp[k]==0) printf("First\n");
	else printf("Second\n");
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < (int)b; i++)
#define all(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const int INF = 1e9;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    int n, m;
    cin >> n >> m;
    int a[n];
    int sum = 0;
    rep(i, 0, n) {
        cin >> a[i];
        sum += a[i];
    }
    int cnt = 0;
    rep(i, 0, n) {
        if (4 * m * a[i] >= sum) cnt++;
    }
    if (cnt >= m) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


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

using namespace std;

void addArray(int dist[],int source[],int n)
{
	for(int i=0;i<n;i++)
	{
		dist[i] += source[i];
	}
}

void setZero(int dist[],int n)
{
	for(int i=0;i<n;i++)dist[i] = 0;
}

bool check(int source[],int val,int n)
{
	for(int i=0;i<n;i++)
	{
		if(source[i] < val)return false; 
	}
	return true;
}

int main()
{
	int N,M,X;
	int cost[12];
	int A[12][12];

	int UNDR[12];
	int sumCost = 0;
	int minCost = -1;

	cin >> N >> M >> X;

	for(int i=0;i<N;i++)
	{
		cin >> cost[i];
		for(int j=0;j<M;j++)
		{
			cin >> A[i][j];
		}
	}

	int COMB_MAX = pow(2,N);

	for(int i=0;i<COMB_MAX;i++)
	{
		int bit = 1;
		sumCost = 0;
		setZero(UNDR,M);
		for(int b=0;b<N;b++)
		{
			int use = ((i & bit)>>b);
			if(use == 1)
			{
				addArray(UNDR,A[b],M);
				sumCost += cost[b];
			}
			bit *= 2;
		}
		if(check(UNDR,X,M))
		{
			if(minCost == -1)minCost = sumCost;
			minCost = min(sumCost,minCost);
		}
	}

	cout << minCost << endl;

	return 0;
}

Measured memory_bytes: 4072