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

using namespace std;

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

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

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

template <class T>
inline T nCr(T n, T r)
{
    T num = 1;
    for (int i = 1; i <= r; ++i)
    {
        num *= (n - i + 1) / i;
    }
    return num;
}
template <class T>
inline T nPr(T n, T r)
{
    r = n - r;
    T sum = 1;
    int i;
    for (i = n; i >= r + 1; --i)
        sum *= i;
    return sum;
}

template <class T>
inline T facctorial(T k)
{
    T sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}

//numeric
template <class T>
inline T gcd(T a, T b)
{
    if (a < b)
    {
        a ^= b;
        b ^= a;
        a ^= b;
    }

    return b ? gcd(b, a % b) : a;
}

template <class T>
inline T lcm(T a, T b)
{
    return a * b / gcd(a, b);
}

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

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

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

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

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

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

int main()
{
    int r;
    cin >> r;
    cout << 3 * r * r << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=(n);i++)
using ll = long long;
const int INF = 1e9;
const int MOD = 1e9+7;

int main(){
    int n,ma,mb;
    cin>>n>>ma>>mb;
    vector<int> a(n+1),b(n+1),c(n+1);
    rep(i,n) cin>>a[i]>>b[i]>>c[i];
    vector<vector<vector<int>>> dat(n+2,vector<vector<int>>(450,vector<int>(450,INF)));
    dat[1][0][0]=0;
    rep(i,n){
        for(int j=0;j<=400;j++){
            for(int k=0;k<=400;k++){
                dat[i+1][j][k]=min(dat[i][j][k],dat[i+1][j][k]);
                dat[i+1][j+a[i]][k+b[i]]=min(dat[i][j][k]+c[i],dat[i+1][j+a[i]][k+b[i]]);
            }
        }
    }
    int ans=INF;
    rep(j,400){
        rep(k,400){
            if(j*mb==k*ma)
                ans=min(ans,dat[n+1][j][k]);
        }
    }
    if(ans==INF) cout<<"-1";
    else cout<<ans;
}

Measured memory_bytes: 37844
#include <iostream>
#include <string>

using namespace std;

int main(){
    string s;cin >> s;
    int ans = 0;
    for(int i=0; i< s.size()/2; i++){
        int j = s.size()-1-i;
        if(s[i] == 'i' || s[i] == 'w') if(s[i] != s[j]) ans++;
        if(s[i] == '(' && s[j] != ')' || s[i] == ')' && s[j] != '(') ans++;
    }
    if(s.size()%2 != 0 && (s[s.size()/2] == '(' || s[s.size()/2] == ')')) ans++;
    cout << ans << endl;
}

Measured memory_bytes: 1180
#include <iostream>			//cout,endl,cin
#include <string>			//string,to_string,stoi
#include <vector>			//vector
#include <algorithm>		//min,max,swap,sort,reverse,lower_bound,upper_bound
#include <utility>			//pair,make_pair
#include <tuple>			//tuple,make_tuple
#include <cstdint>			//int64_t,int*_t
#include <cstdio>			//printf
#include <map>				//map
#include <queue>			//queue,priority_queue
#include <set>				//set
#include <stack>			//stack
#include <deque>			//deque
#include <unordered_map>	//unordered_map
#include <unordered_set>	//unordered_set
#include <bitset>			//bitset
#include <cctype>			//isupper,islower,isdigit,toupper,tolower
#include <math.h>
#include <cstdio>
#include <cstring>
#include <iomanip>

using namespace std;

int main(void){
	int a, b, c, d;
	int v = 0;
	cin >> a >> b >> c >> d;
	while (1) {
		c = c - b;
		if (c <= 0) {
			v = 1;
			break;
		}
		a = a - d;
		if (a <= 0) {
			v = 0;
			break;
		}
	}
	if (v == 1) {
		cout << "Yes" << endl;
	}
	else if (v == 0) {
		cout << "No" << endl;
	}


}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,K;cin>>K>>N;int A[N];
  for(int i=0;i<N;i++)cin>>A[i];
  int M=A[N-1]-A[0];
  for(int i=1;i<N;i++)M=min(M,K-A[i]+A[i-1]);
  cout<<M<<endl;
}

Measured memory_bytes: 1024
import itertools

n,c = map(int, input().split())
d = [list(map(int, input().split())) for i in range(c)]
e = [list(map(int, input().split())) for i in range(n)]

x = [0 for i in range(c)]
y = [0 for i in range(c)]
z = [0 for i in range(c)]

for i in range(n):
    for j in range(n):
        if (i+j+2)%3 == 0:
            x[e[i][j]-1] += 1
        elif (i+j+2)%3 == 1:
            y[e[i][j]-1] += 1
        else:
            z[e[i][j]-1] += 1

f = [i for i in range(c)]

g = list(itertools.permutations(f,3))

ans = float('inf')
for i in range(len(g)):
    a = 0
    for j in range(c):
        a += d[j][g[i][0]]*x[j] + d[j][g[i][1]]*y[j] + d[j][g[i][2]]*z[j]
    ans = min(ans, a)

print(ans)

Measured memory_bytes: 47068
// list
#include <cstdio>
#include <list>
#include <algorithm>
using namespace std;

int main(){
    int q,x;
    char com[20];
    // list from standard library
    list<int> v;
    scanf("%d", &q);
    for(int i=0; i<q; i++){
        scanf("%s", com);
        if(com[0] == 'i'){
            scanf("%d", &x);
            v.push_front(x);
        } else if(com[6] == 'L'){
            v.pop_back();
        } else if(com[6] == 'F'){
            v.pop_front();
        } else if(com[0] == 'd'){
            scanf("%d", &x);
            for(list<int>::iterator it = v.begin(); it!=v.end(); it++){
                if(*it == x){
                    v.erase(it);
                    break;
               }
            }
        }
    }
    int i=0;
    for(list<int>::iterator it = v.begin(); it!=v.end(); it++){
        if(i++){printf(" ");}
        printf("%d", *it);
    }
    printf("\n");

    return 0;
}


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

int main(){
  int N,maxA=0,minA=1e9+7;
  cin >> N;
  for(int i=0;i<N;i++){
    int A;
    cin >> A;
    maxA=max(maxA,A);
    minA=min(minA,A);
  }
  cout << maxA-minA << endl;
}

Measured memory_bytes: 3632
#include<stdio.h>
int main(){
  int n,i,m,j,t;
  unsigned long c;
  int d[10000];
  while(1){
    scanf("%d",&n);
    if(n==0)break;
    for(i=0;i<n;i++){
      scanf("%d",&d[i]);
    }
    for(i=0;i<n;i++){
      for(j=1;i+j<n;j++){
	if(d[j-1]>d[j]){
	  t=d[j];
	  d[j]=d[j-1];
	  d[j-1]=t;
	}
      }
    }
    c=0;
    for(i=0;i<n-1;i++){
      c+=(n-i-1)*d[i];
    }
    printf("%ld\n",c);
  }
  return 0;
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
  static String s;

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

    s = sc.next();

    char[] t = new char[s.length()];
    for(int i = 0; i < s.length(); i++){
      t[i] = (i % 2 == 0 ? 'g' : 'p');
    }

    int score = 0;
    for(int i = 0; i < s.length(); i++){
      char ch = s.charAt(i);
      if(ch == 'g' && t[i] == 'p'){
        ++score;
      }
      else if(ch == 'p' && t[i] == 'g'){
        --score;
      }
    }

    System.out.println(score);
  }
}


Measured memory_bytes: 13976
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <functional>
#include <iomanip>
#include <bitset>
#include <numeric>
#include <queue>
#include <map>
#include <cstdint>
using namespace std;
#define rep(i, n) for (ll i = 0; i < n; i++)
const long long mod = 1000000007;
typedef long long int ll;
typedef pair<ll, ll> P;
const vector<int> di = { -1, 0, 1, 0 };
const vector<int> dj = { 0, 1, 0, -1 };


int main() {

	int n, m;
	cin >> n >> m;
	vector<P> p(n);
	rep(i, n) cin >> p[i].first >> p[i].second;
	vector<P> q(m);
	rep(i, m) cin >> q[i].first >> q[i].second;

	rep(i, n) {
		P num;
		num.first = 0;
		num.second = mod;
		rep(j, m) {
			int dist = abs(p[i].first - q[j].first) + abs(p[i].second - q[j].second);
			if (dist < num.second) {
				num.first = j + 1;
				num.second = dist;
			}
		}
		cout << num.first << endl;
	}

	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int main()
{
	char c;
 	cin >> c;
  	if(c == 'A')
      cout << "T" << endl;
  	else if(c == 'T')
      cout << "A" << endl;
  	else if(c == 'C')
      cout << "G" << endl;
  	else
      cout << "C" << endl;
 	return 0; 
}

Measured memory_bytes: 256
N = int(input())
if N == 2:
    print(2)
    exit()
ans = float('inf')
for i in range(2,N):
    A = i
    B = N - i
    tmp = 0
    for k in str(A):
        tmp += int(k)
    for k in str(B):
        tmp += int(k)
    ans = min(ans,tmp)
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>pi;
const int MAXN=100005;
const int MOD=1000000007;

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define DEC(i,a,b) for(int i=(a);i>=(b);i--)
#define fst first
#define snd second
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#define db(x) cerr<<#x<<" = "<<x<<"\n"
#define LOW(v,x) (lower_bound(all(v),(x))-(v).begin())
#define UP(v,x) (upper_bound(all(v),(x))-(v).begin())

int maxchar(string x){
	int tmp=0;
	for (auto c:x){
		tmp = max(tmp, (int) c-'a');
	}
	return tmp;
}
main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int N;cin>>N;
	set<string> S;
	S.insert("a");
	FOR(i,2,N){
		set<string> newS;
		for(auto j:S){
			FOR(i,0,maxchar(j)+1){
				char c='a'+i;
				string k=j+c;
				newS.insert(k);
			}
		}
		swap(S,newS);
	}
	for(auto i:S) cout<<i<<"\n";
}


Measured memory_bytes: 14720
//#define _GLIBCXX_DEBUG//実行時、何も出なかったらこれを使う
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<numeric>
#include<climits>
#include<limits>//
#include <stdio.h>//

using namespace std;

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

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

int dy[] = {1,0}; //次に行くところ
int dx[] = {0,1}; //上に同じ


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

  int h, w, k;
  cin >> h >> w >> k;

  vector<string> c(h);

  rep(i,h){
    cin >> c[i];
  }

  int res = 0;

  for(int bit1 = 0; bit1 < 1 << h; ++bit1){
    for(int bit2 = 0; bit2 < 1 << w; ++bit2){
      int cnt = 0;
      for(int i = 0; i < h; ++i){
        for(int j = 0; j < w; ++j){
          if(c[i][j] == '#' && (bit1 & 1 << i) == 0 && (bit2 & 1 << j) == 0){
            ++cnt;
          }
        }
      }
      if(cnt == k){
        ++res;
      }
    }
  }

  cout << res << '\n';
  
  return 0;
}

Measured memory_bytes: 3652
from copy import deepcopy

H, W, K = map(int, input().split())
puzzle = [[-1] * H for _ in range(W)]

for i in range(H - 1, -1, -1):
    for j, stone in enumerate(list(map(int, input()))):
        puzzle[j][i] = stone


def solve(h, w):
    pz = deepcopy(puzzle)
    pz[w].pop(h)
    pz[w].append(0)
    ans = 0
    cnt = 0
    tmp_score = -1
    while tmp_score != 0:
        tmp_score = 0
        tmp_sum = 0

        # puzzle連鎖確認
        for i in range(H - 1, -1, -1):
            ch_cnt = 0
            for j in range(W - 1):
                if pz[j][i] == pz[j + 1][i]:
                    ch_cnt += 1
                else:
                    if ch_cnt + 1 >= K:
                        # 得点
                        tmp_sum += pz[j][i] * (ch_cnt + 1)
                        # puzzle消去
                        for p in range(j, j - (ch_cnt + 1), -1):
                            pz[p].pop(i)
                            pz[p].append(0)
                    ch_cnt = 0
            else:
                if ch_cnt + 1 >= K:
                    # 得点
                    tmp_sum += pz[j][i] * (ch_cnt + 1)
                    # puzzle消去
                    for p in range(j + 1, j - ch_cnt, -1):
                        pz[p].pop(i)
                        pz[p].append(0)
        tmp_score += (2 ** cnt) * tmp_sum
        cnt += 1
        ans += tmp_score
    return ans


f_ans = 0
for i in range(H):
    for j in range(W):
        f_ans = max(f_ans, solve(i, j))


print(f_ans)


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

int main(){
	int a,b;
	int ram=12;
	int raM=13;
	int rb=10;
	int j=0;
	int i=0;
	int x;
	int y;
	cin>>a>>b;
	ram=a*ram;
	raM=raM*a;
	rb=rb*b;
	if(ram>rb) x=rb;
	if(ram<=rb) x=ram;
	if(raM<=rb) y=rb;
	if(raM>=rb) y=raM;
	for(i=x;i<y+1;i++){
		if(i*10/100==b && i*8/100==a){
			cout<<i;
			j=1;
			break;
		}
	}
	if(j==0) cout<<-1;

}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

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

	int totalPerson = 0;
	for (int i = 0; i < N; i++) {
		int l, r;
		cin >> l >> r;
		totalPerson = totalPerson + (r - l + 1);
	}

	cout << totalPerson << endl;

}


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

const int N=105;
int n,p,i,x;
long long f0,f1,tmp;
int main()
{
	cin>>n>>p;
	for(i=1,f0=1;i<=n;i++)
	{
		cin>>x;
		x&=1;
		if(x)
		{
			tmp=f0;
			f0+=f1;
			f1+=tmp;
		}
		else
		{
			f0=f0*2;
			f1=f1*2;
		}
	}
	if(p)cout<<f1;
	else cout<<f0;
	return 0;
}


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

#define fto(i, a, b) for(int i = a; i <= b; ++i)
#define fdto(i, a, b) for(int i = a; i >= b; --i)
#define ff first
#define ss second
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define pb push_back
#define oo 1000000007
#define OO 1000000000000000007

using namespace std;

int main() {
    char x, y;
    cin >> x >> y;
    if (x == '9' || y == '9') puts("Yes");
    else puts("No");
    return 0;
}
///12436


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

using namespace std;

int main() {
    int n;

    cin >> n;

    while (n--) {
        int a[3];

        cin >> a[0] >> a[1] >> a[2];
        sort(a, a + 3);

        if (a[2] * a[2] == a[0] * a[0] + a[1] * a[1]) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 1168
fun main(args : Array<String>) {
    val n = readLine()!!.toInt()
    val aa = readLine()!!.split(" ").map { it.toInt() }

    var isDropping = true
    var cash = 1000L
    var stocks = 0L

    for (i in 0 until n-1) {
        if (isDropping && aa[i] < aa[i+1]) {
            // cheapest atm
            stocks += cash / aa[i]
            cash -= (cash / aa[i]) * aa[i]
            isDropping = false

        } else if (!isDropping && aa[i] > aa[i+1]) {
            // highest atm
            cash += stocks * aa[i]
            stocks = 0
            isDropping = true
        }
    }

    // sell all the rest
    cash += stocks * aa[n-1]
    println(cash)
}

Measured memory_bytes: 36424
#include<stdio.h>
int main(void){
 int N,A,B,min;
 while(1){
   scanf("%d",&N);
   scanf("%d",&A);
   scanf("%d",&B);
   if( (1<=N<=20)&&(1<=A<=200)&&(1<=B<=2000) ) break;
 }
 if(A*N>=B) min = B;
 if(B>=A*N) min = A*N;
 printf("%d",min);
 return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main ()
{
	int n,m,b,x;
	scanf ("%d",&n);
	if (n>=100 &&n<=999)
	{
	m = n%10;
	b =n/10;
	x = b/10;
	if (m ==x )
	printf ("Yes\n");
	else printf ("No\n");
}
else ;
}

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

int N ;
int main ()
{
scanf("%d",&N);
int res = N ;
for ( int i =0; i <= N ; i ++)
{
int cc =0;
int t = i ;
while (t >0) cc += t %6 , t /=6;
t=N - i ;
while (t >0) cc += t %9 , t /=9;
if ( res > cc ) res = cc ;
}
printf("%d\n",res);
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string.h>

using namespace std;
static const int MAXV = 21;

int main() {
  char A[MAXV]={};
  cin >> A;
  int i=0;
  for(;i<MAXV;i++) {
    //printf("%c", A[i]);
    if (A[i] == 0) break;
  }
  i--;
  for(;i!=-1;i--) {
    printf("%c", A[i]);
  }
  printf("\n");
}

Measured memory_bytes: 0
#include <iostream>
using namespace std;
int main(void){
  int a,b;
  cin >> a >> b;

  int p,q,r,s,t;
  int ans = 0;

  //cout << "DO" << endl;

  for(int j=a;j<=b;j++){
    int i = j;
    p = i / 10000;
    if(i % 10 == p){
      t = i % 10;
      i /= 10;
      s = i % 10;
      i /= 10;
      r = i % 10;
      i /= 10;
      q = i % 10;
    if(p == t && q == s)
      ans++;
  }
  }


  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define uint unsigned
#define pii pair<int,int>
#define pll pair<ll,ll>
#define IT iterator
#define PB push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define UPD(x,y) (((x)+=(y))>=mo?x-=mo:233)
#define CLR(a,v) memset(a,v,sizeof(a));
#define CPY(a,b) memcpy(a,b,sizeof(a));
#define debug puts("wzpakking")
using namespace std;
const int N=100005;
int n,m,nn;
vector<pii> vec[N];
ll tg[N*4],val;
void build(){
	for (nn=1;nn<=n+1;nn<<=1);
	For(i,0,2*nn-1) tg[i]=1ll<<60;
	tg[1+nn]=0;
}
void change(int x,int y,ll v){
	x+=nn-1; y+=nn+1;
	for (;x^y^1;x>>=1,y>>=1){
		if (!(x&1)) tg[x^1]=min(tg[x^1],v);
		if (y&1) tg[y^1]=min(tg[y^1],v); 
	}
}
ll ask(int x){
	ll ans=1ll<<60;
	for (x+=nn;x;x>>=1)
		ans=min(ans,tg[x]);
	return ans;
}
int main(){
	scanf("%d%d",&n,&m);
	For(i,1,m){
		int x,y,v;
		scanf("%d%d%d",&x,&y,&v);
		vec[x].PB(pii(y,v));
	}
	build();
	For(i,1,n){
		val=ask(i);
		For(j,0,vec[i].size()-1)
			change(i,vec[i][j].fi,val+vec[i][j].se);
	}
	if (val>=1ll<<59) puts("-1");
	else printf("%lld\n",val);
}

Measured memory_bytes: 8832
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <stdio.h>
#include <string.h>

using namespace std;

static const double EPS = 1e-9;
template<class T> bool INRANGE(T x, T a, T b) { return a <= x && x <= b; }
template<class T> void amin(T &a, T v) { if (a > v) a = v; }
template<class T> void amax(T &a, T v) { if (a < v) a = v; }
int ROUND(double x) { return (int)(x + 0.5); }
bool ISINT(double x) { return fabs(ROUND(x) - x) <= EPS; }
bool ISEQUAL(double x, double y) { return fabs(x - y) <= EPS * max(1.0, max(fabs(x), fabs(y))); }
double SQSUM(double x, double y) { return x * x + y * y; }
#define PI  (acos(-1))
#define ARRAY_NUM(a) (sizeof(a)/sizeof(a[0])) 
#define NG (-1)
#define BIG ((int)1e9+10)
#define BIGLL ((ll)4e18)
#define SZ(a) ((int)(a).size())
#define SQ(a) ((a)*(a))
typedef unsigned long long ull;
typedef long long ll;


#define MAXN 100005

int n, a[MAXN], b[2 * MAXN], s;
ll total;

int query(int p) {
	int t = 0;
	for (int i = (p + MAXN); i; i -= (i & -i)) {
		t += b[i];
	}
	return t;
}
void update(int p) {
	for (int i = (p + MAXN); i < 2 * MAXN; i += (i & -i)) {
		b[i]++;
	}
}

ll getTotal(int x, const vector <int>& c)
{
	total = 0;
	s = 0;
	memset(a, 0, sizeof(a));
	memset(b, 0, sizeof(b));

	for (int i = 0; i<n; ++i) {
		a[i] = (c[i] >= x ? 1 : -1);
	}
	update(0);

	for (int i = 0; i<n; ++i) {
		s += a[i];
		total += query(s);
		update(s);
	}

	return total;
}

int main() 
{
	cin >> n;

	vector <int> c(n);

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


	vector <int> d(c);
	sort(d.begin(), d.end());

/*
	for (int i = 0; i < n; ++i)
	{
		ll aboveXTotal = getTotal(d[i], c);
		// BEGIN CUT HERE
		cerr << " i=" << i << " d[i]=" << d[i] << " aboveXTotal=" << aboveXTotal << endl;
		// END CUT HERE


	}
	*/

	ll rank = (ll)n * (n + 1LL) / 2 / 2;

	ll lo = 0;
	ll hi = n - 1;
	// BEGIN CUT HERE
//	cerr << " rank=" << rank << endl;
	// END CUT HERE

	while (lo<hi)
	{
		ll mid = lo + (hi - lo + 1) / 2LL; // +1 is necessary, otherwise infinite loop when only two elements.

		ll aboveXTotal = getTotal(d[mid], c);


		// BEGIN CUT HERE
//		cerr << " lo=" << lo << " hi=" << hi << " mid=" << mid << " d[mid]=" << d[mid] << " aboveXTotal=" << aboveXTotal << endl;
		// END CUT HERE




		if (aboveXTotal < rank)
		{
			hi = mid - 1;
		}
		else
		{
			lo = mid;
		}
	}


	cout << d[lo] << endl;



	return 0;
}



Measured memory_bytes: 2176
from sys import stdin

def main():
    N, M = map(int, input().split())
    LR = [tuple(map(int, input().split())) for _ in [0] * M]

    l, r = list(zip(*LR))
    lmax = max(l)
    rmin = min(r)
    ans = 0
    for i in range(lmax, rmin + 1):
        if i <= N:
            ans += 1
    print(ans)

input = lambda: stdin.readline()
main()


Measured memory_bytes: 25168
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define erep(i,a,b) for(int i=a;i<=(int)(b);++i)
#define per(i,a,b) for(int i=(b);i>(a);--i)
#define eper(i,a,b) for(int i=((int)(a));i>=b;--i)
#define pb push_back
#define mp make_pair
#define INF 2000000000
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a, b)*b;}

int n, toE[300005], toW[300005], ans;
string s;
int main() {
 ios::sync_with_stdio ( false );
 cin.tie ( 0 );
    ans = INF;
    cin >> n >> s;
    toE[0] = 0, toW[n] = 0;
    erep(i, 1, n) {
        if (s[i-1] == 'W') toE[i] = toE[i-1] + 1;
        else toE[i] = toE[i-1];
    }
    eper(i, n-1, 0) {
        if (s[i+1] == 'E') toW[i] = toW[i+1] + 1;
        else toW[i] = toW[i+1];
    }
    rep(i, 1, n) ans = min(ans, toE[i]+toW[i]);
    ans = min(toW[0], ans); ans = min(toE[n], ans);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 2964
#include<iostream>
using namespace std;
int main(){
  int a,b;
  cin>>a>>b;
  int n;
  if(b<10){
    n=10*a+b;
  }else if(b<100){
    n=100*a+b;
  }else{
    n=1000*a+b;
  }
  int s[321];
  for(int i=1;i<=320;i++)s[i]=i*i;
  for(int i=1;i<=320;i++){
    if(n==s[i]){
      cout<<"Yes";
      return 0;
    }
  }
  cout<<"No";
  return 0;
}

Measured memory_bytes: 256
def resolve():
    import sys
    sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
    to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
    print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数
    print_list_with_space = lambda x: print(*x, sep=" ")

    # 入力を整数に変換して受け取る
    def input_int(): return int(input())

    def map_int_input(): return map(int, input())

    MII = map_int_input

    def MII_split(): return map(int, input().split())

    def MII_to_index(): return map(to_index, input())

    def MII_split_to_index(): return map(to_index, input().split())

    # 入力全てを整数に変換したものの配列を受け取る
    def list_int_inputs(): return list(map(int, input()))

    LII = list_int_inputs

    def LII_split(): return list(map(int, input().split()))

    # 2次元リスト化
    def LII_2D(rows_number): return [LII() for _ in range(rows_number)]

    def LII_split_2D(rows_number): return [LII_split() for _ in range(rows_number)]

    N = input_int()
    a_list = LII_split()
    b_list = []

    xor_all = a_list[0]
    for a in a_list[1:]:
        xor_all ^= a

    for a in a_list:
        b_list.append(a^xor_all)
    # print(b_list)
    print_list_with_space(b_list)
    
resolve()

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

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

	unsigned long long sum = 0;
	for (auto c : s) {
		sum += c - '0';
	}


	if (sum % 9 == 0) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}


	return 0;
}

Measured memory_bytes: 3744
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

void caesar(char* a)
{
	for (int i=0; i<strlen(a); i++) {
		if (a[i] == ' ' || a[i] == '.') continue;
		else if (a[i] == 'z') a[i] = 'a';
		else a[i]++;
	}
}

int main()
{
	char buf[81];
	
	while ( cin.getline(buf, sizeof(buf)) ) {
		int len = strlen(buf);
		for (int i=0; i<26; i++) {
			if ( (strstr(buf, "the") != NULL) || (strstr(buf, "this") != NULL) || (strstr(buf, "that") != NULL) ) {
				cout << buf << endl;
				break;
			}
			caesar(buf);
		}
	}
	
	return 0;
}

Measured memory_bytes: 3008
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define fore(i, b, e) for (int i = (int)(b); i <= (int)(e); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long i64;
typedef unsigned long long u64;
typedef long double ld;
typedef long long ll;
// #define sz(x) int((x).size())

const int mod = 1000000007;

int add(int x, int y) { x += y; if (x >= mod) x -= mod; return x; }
int mul(i64 x, i64 y) { return x*y%mod; }

int n;
int a[100500];
int b[100500];
int c[100500];

void no() { cout << 0; exit(0); }

void tr(int i, int x) {
    if (c[i] == 0 || c[i] == x) c[i] = x;
    else no();
}

void solve() {
    scanf("%d", &n);
    forn(i, n) scanf("%d", &a[i]);
    forn(i, n) scanf("%d", &b[i]);
    c[0] = a[0];
    forn(i, n) if (i && a[i] > a[i-1]) c[i] = a[i];

    tr(n-1, b[n-1]);
    for (int i = n-2; i >= 0; --i) if (b[i] > b[i+1]) tr(i, b[i]);

    int mx;
    mx = 0;
    forn(i, n) {
        mx = max(mx, c[i]);
        if (mx != a[i]) no();
    }
    mx = 0;
    ford(i, n) {
        mx = max(mx, c[i]);
        if (mx != b[i]) no();
    }

//     forn(i, n) cerr << c[i] << " "; cerr << endl;

    int res = 1;
    forn(i, n) if (!c[i]) res = mul(res, min(a[i], b[i]));
    cout << res << endl;
}

int main() {
#ifdef LOCAL
    freopen("c.in", "r", stdin);
#endif

    solve();

#ifdef LOCAL
    cerr << "Time elapsed: " << clock() / 1000 << " ms" << endl;
#endif
    return 0;
}


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

int main() {
	stack<int> S1;
	stack<pair<int, int> > S2;
	char ch;
	int sum = 0;
	for (int i = 0; cin >> ch; i++) {
		if (ch == '\\') S1.push(i);
		else if (ch == '/'&& S1.size() > 0) {
			int j = S1.top(); S1.pop();
			sum += i - j;
			int a = i - j;
			while (S2.size() > 0 && S2.top().first > j) {
				a += S2.top().second; S2.pop();
			}
			S2.push(make_pair(j, a));
		}
	}

	vector<int> ans;
	while (S2.size() > 0) {
		ans.push_back(S2.top().second);
		S2.pop();
	}
	reverse(ans.begin(), ans.end());
	cout << sum << endl;
	cout << ans.size();
	for (int i = 0; i < ans.size(); i++) {
		cout << " ";
		cout << ans[i];
	}
	cout << endl;
	return 0;
}


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

int main() {
  ll a;
  double b;
  cin >> a >> b;
  ll llb = b*100+0.1;
  a *= llb;
  a /= 100;
  cout << a << endl;
  return 0;
}


Measured memory_bytes: 3716
#include <iostream>

using namespace std;

int main(){
  int a, b;
  cin >> a >> b;
  if(a == b) {
    cout << "Draw" << endl;
  } else if(a == 1) {
    cout << "Alice" << endl;
  } else if(b==1) {
    cout << "Bob" << endl;
  } else if(a < b) {
    cout << "Bob" << endl;
  } else {
    cout << "Alice" << endl;
  }
  return 0;
}


Measured memory_bytes: 3596
#include<stdio.h>
int main(void)
{
	int n, k;
	scanf("%d", &n);
	scanf("%d", &k);

	int i;
	int count = 0;
	for (i = 1; i <= n; i++) {
		if (i + (k - 1) <= n) {
			count++;
		}
	}
	printf("%d\n", count);
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ul;
#define all(x) (x).begin(), (x).end()
#define pi 3.1415926536

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x): val(x), left(NULL), right(NULL){}
};

struct ListNode {
    int val;
    ListNode* next;

    ListNode(int x): val(x), next(NULL){}
};

int nxt(){
    int x;
    cin>>x;
    return x;
}

ll nxtLong(){
    ll x;
    cin>>x;
    return x;
}

string nxtStr(){
    string x;
    cin>>x;
    return x;
}

char nxtChar(){
    char x;
    cin>>x;
    return x;
}

double nxtDouble(){
    double x;
    cin>>x;
    return x;
}

ld nxtLDouble(){
    ld x;
    cin>>x;
    return x;
}

TreeNode* makeTree(int n){
    queue<TreeNode*> tree_nodes;
    TreeNode* root;
    if(n){
        root = new TreeNode(nxt());
        tree_nodes.push(root);
    }else{
        return NULL;
    }
    while(!tree_nodes.empty()){
        TreeNode* node = tree_nodes.front();
        tree_nodes.pop();
        bool left;
        cin>>left;
        if(left){
            node->left = new TreeNode(nxt());
            tree_nodes.push(node->left);
        }
        bool right;
        cin>>right;
        if(right){
            node->right = new TreeNode(nxt());
            tree_nodes.push(node->right);
        }
    }
    return root;
}

ListNode* makeLinkedList(int n){
    ListNode* list = new ListNode(0);
    ListNode* dummy = list;

    for(int i=0;i<n;++i){
        list->next = new ListNode(nxt());
        list = list->next;
    }

    return dummy->next;
}

void solve(){
    int n = nxt();

    vector<int> in(n);

    map<int,int> mp1,mp2;
    for(int i=0;i<n;++i){
        cin>>in[i];
        if(i%2){
            mp1[in[i]]++;
        }else{
            mp2[in[i]]++;
        }
    }

    vector<pair<int,int>> one, two;
    int ans = INT_MAX;

    for(int i=1;i<=100000;++i){
        one.push_back({mp1[i], i});
        two.push_back({mp2[i], i});
    }
    sort(all(one), greater<pair<int,int>>());
    sort(all(two), greater<pair<int,int>>());
    if(one[0].second != two[0].second){
        ans = min(ans, n-one[0].first-two[0].first);
    }else{
        ans = min(ans, n-one[1].first-two[0].first);
        ans = min(ans, n-one[0].first-two[1].first);
    }
    cout<<ans<<endl;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout<<fixed<<setprecision(9);
    //ll t;
    //cin>>t;
    //while(t--){
    //    solve();
    //}
    solve();
    return 0;
}


Measured memory_bytes: 14608
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
	Main m = new Main();
	m.answer();
    }

    private Scanner scan = new Scanner(System.in);
    private static final int MAX = 3500;
    private int N;

    public Main() {
	N = Integer.parseInt(scan.next());
	scan.close();
    }

    public final void answer() {
	for (int h = Integer.max(1, N/4); h <= MAX; h++) {
	    if(4*h-N > 0) {
		for (int n = Integer.max(1, N*h/(4*h-N)); n <= MAX; n++) {
		    long a = (long)N*h*n;
		    long b = (long)4*h*n-(long)N*(n+h);
		    if(b > 0 && a > b && a%b == 0) {
			long w = a/b;
			System.out.println(String.valueOf(h) + ' ' + n + ' ' + w);
			return;
		    }
		}
	    }
	}
    }
}


Measured memory_bytes: 23124
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

typedef long long ll;

const int MAXN = 2010;
const int MAXM = 40010;
const ll INF = 1ll << 60;

struct Edge
{
	int to;
	ll cap;
	ll val;
	int nxt;
}edge[MAXM];

int n,W,id = 1,S,T,tot;
int a[MAXN];
int first[MAXN];

ll dis[MAXN];

bool vis[MAXN];
bool inqueue[MAXN];

queue<int> Q;

pair<int,int> v[MAXN];

void addE(int u,int v,ll c,ll w)
{
	edge[++id] = (Edge){v,c,w,first[u]};
	first[u] = id;
	edge[++id] = (Edge){u,0,-w,first[v]};
	first[v] = id;
}

ll SPFA()
{
	for (int i = S;i <= T;i++)
		dis[i] = -INF;
	dis[S] = 0;
	Q.push(S);
	inqueue[S] = 1;
	while (!Q.empty())
	{
		int u = Q.front();
		Q.pop();
		inqueue[u] = 0;
		for (int i = first[u];i;i = edge[i].nxt)
			if (edge[i].cap > 0 && dis[edge[i].to] < dis[u] + edge[i].val)
			{
				dis[edge[i].to] = dis[u] + edge[i].val;
				if (!inqueue[edge[i].to])
				{
					Q.push(edge[i].to);
					inqueue[edge[i].to] = 1;
				}
			}
	}
	return dis[T];
}

ll dfs(int u,ll f,ll &tot)
{
	if (u == T)
		return f;
	vis[u] = 1;
	ll res = 0;
	for (int i = first[u];i;i = edge[i].nxt)
		if (!vis[edge[i].to] && edge[i].cap > 0 && dis[edge[i].to] == dis[u] + edge[i].val)
		{
			ll ret = dfs(edge[i].to,min(edge[i].cap,f),tot);
			edge[i].cap -= ret;
			edge[i ^ 1].cap += ret;
			f -= ret;
			res += ret;
			tot += ret * edge[i].val;
			if (!f)
				break;
		}
	return res;
}

ll mcmf()
{
	ll res = 0;
	while (SPFA() > 0)
	{
		memset(vis,0,sizeof(vis));
		dfs(S,INF,res);
	}
	return res;
}

int main()
{
	scanf("%d",&n);
	S = 0,T = 2 * n + 5;
	for (int a,b,c,i = 1;i <= n;i++)
	{
		scanf("%d%d%d",&b,&c,&a);
		addE(S,i,a,0);
		addE(i,2 * n + 1,INF,b + c);
		addE(i,2 * n + 2,INF,b - c);
		addE(i,2 * n + 3,INF,c - b);
		addE(i,2 * n + 4,INF,-b - c);
	}
	for (int a,b,c,i = 1;i <= n;i++)
	{
		scanf("%d%d%d",&b,&c,&a);
		addE(i + n,T,a,0);
		addE(2 * n + 1,i + n,INF,-b - c);
		addE(2 * n + 2,i + n,INF,c - b);
		addE(2 * n + 3,i + n,INF,b - c);
		addE(2 * n + 4,i + n,INF,b + c);
	}
	printf("%lld\n",mcmf());
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;

#define ll long long

ll MAX(ll a, ll b) {

	if (a > b)return a;
	else return b;

}
ll MIN(ll a, ll b) {

	if (a < b)return a;
	else return b;

}
ll powsur(ll a, ll b, ll p) {

	if (b == 0) {

		return 1;

	}
	else if (b % 2 == 0) {

		ll d = powsur(a, b / 2, p);
		return ((d%p)*(d%p)) % p;

	}
	else {

		return ((a%p)*powsur(a, b - 1, p) % p) % p;

	}

}
//pは素数,aのb乗をpで割った余り

ll CMOD(ll n, ll r, ll p) {

	ll a = 1, b = 1, c = 1, re;
	for (int i = 1; i <= n; i++) {

		a *= i;
		a = a%p;

	}
	for (int i = 1; i <= r; i++) {

		b *= i;
		b = b%p;

	}
	for (int i = 1; i <= n - r; i++) {

		c *= i;
		c = c%p;

	}
	b = powsur(b, p - 2, p);
	c = powsur(c, p - 2, p);
	re = ((a%p)*(b%p)) % p;
	re = ((re%p)*c%p) % p;

	return re;

}
//pは素数,(nCr)%p

ll gcd(ll a, ll b) {

	if (a < b) {

		ll tmp = a;
		a = b;
		b = tmp;

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

}
//最大公約数

ll lcm(ll a, ll b) {

	return a / gcd(a, b)*b;

}
//最小公倍数

int main() {
	
	ll N;
	cin>>N;
	if(N%2==0)cout<<N<<endl;
	else cout<<N*2<<endl;

	return 0;
}

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

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

    for(int i=0; i<=n/7; i++){
        if((n - 7 * i) % 4 == 0){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

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

#define pii pair <int, int>
#define pb push_back
#define ll long long
#define ss second
#define ff first
#define N 100010

using namespace std;

ll n, k;

int main()
{
	cin >> n >> k;
	
	if (k == 0) {
		cout << n*n;
		return 0;
	}
	
	ll ans = (n - k + 1) * 1LL * (n - k) / 2;
	for(int i = k + 1; i+k <= n; i++) {
		int ret = (n-i-k)/i;
		ans += ret * (i - k);
		
		int a = i+k;
		
		if (ret*i+a + (i-k-1) <= n)
			ans += i-k;
		else
			ans += n-(ret*i+a)+1;
	}
	
	cout << ans;
}

Measured memory_bytes: 256
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    int N;
    cin >> N;

    map<char, int> m;
    REP(i, N) {
        string s; cin >> s;

        if (i == 0) {
            REP(i, s.size()) ++m[s[i]];
            continue;
        }

        map<char, int> tmp;
        REP(i, s.size()) {
            ++tmp[s[i]];
        }

        for(auto it=m.begin(); it != m.end(); ++it) {
            char c = it->fi;
            int cnt = it->se;
            m[c] = min(cnt, tmp[c]);
        }
    }

    for(auto it=m.begin(); it != m.end(); ++it) {
        char c = it->fi;
        int cnt = it->se;
        REP(i, cnt) cout << c;
    }
    cout << endl;
    
}


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

int main()
{
    int H, W;
    cin >> H >> W;
    vector<string> A(H);
    cin.ignore();
    for (int i = 0; i < H; i++)
    {
        getline(cin, A[i]);
    }

    for (int i = 0; i < W + 2; i++)
    {
        cout << '#';
    }
    cout << endl;
    for (int i = 0; i < H; i++)
    {
        cout << '#' << A[i] << '#' << endl;
    }
    for (int i = 0; i < W + 2; i++)
    {
        cout << '#';
    }

    return 0;
}

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

struct edge{
  int to;
  int cost;
};

int ans[100010];
vector<vector<edge>> g;

void bfs(int s){
  queue<int> q;
  q.push(s);
  ans[s]=0;
  while(!q.empty()){
    int p = q.front();q.pop();
    for(int i=0;i<g[p].size();++i){
      if(ans[g[p][i].to]<1e5) continue;
      ans[g[p][i].to]= (g[p][i].cost%2==0 ? (ans[p]) : (!ans[p]));
      q.push(g[p][i].to);
    }
  }
}

int main(){
  ll N;cin>>N;
  g.resize(N);
  fill(ans,ans+100010,1e5);
  rep(i,N-1){
    int u,v,w;cin>>u>>v>>w;u--,v--;
    edge e1={v,w},e2={u,w};
    g[u].push_back(e1);
    g[v].push_back(e2);
  }
  bfs(0);
  rep(i,N) cout<<ans[i]<<endl;
}

Measured memory_bytes: 6784
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
ll INFL = 1000000000000000010;//10^18 = 2^60
int INF = 2147483600;//10^9
ll MOD  = 1000000007;
int N,A,B,C;
vector<int> l(1010);



int main(void){
    // Your code here!
    cin >> N >> A >> B >> C;
    for(int i = 0; i < N; i++) cin >> l.at(i);
    vector<int> ABC(N); //0123　🙅ABC
    int ans = INF;
    
    
    for(int i = 0; i < pow(4, N); i++){
        int I = i;
        int a=0,b=0,c=0;
        for(int j = 0; j < N; j++){
            ABC.at(j) = I % 4;
            I /= 4;
        }
        
        //Aの竹を作る
        int A_copy = A,B_copy = B, C_copy = C;
        int ans_now = -30;
        
        for(int j = 0; j < N; j++){
            if(ABC.at(j) == 1){
                A_copy -= l.at(j);
                ans_now += 10;
                a++;
            }
            else if(ABC.at(j) == 2){
                B_copy -= l.at(j);
                ans_now += 10;
                b++;
            }else if(ABC.at(j) == 3){
                C_copy -= l.at(j);
                ans_now += 10;
                c++;
            }
        }
        if(a == 0 || b == 0 || c == 0) continue;
        ans_now += abs(A_copy) + abs(B_copy) + abs(C_copy);
        
        
        
        ans = min(ans, ans_now);
    }
    cout << ans << endl;
    
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define point complex<double>
const long long N = 3e3+5,mod=1e9+7;
typedef long long ll;
ll fact[N],inv[N];
ll fp(ll num,ll p){
if(p==0)return 1;
ll ans=fp(num,p/2);
ans=(ans*ans)%mod;
if(p%2!=0)
    ans=(ans*(num%mod))%mod;
return ans;
}
ll ncr(int n ,int m){
return (((fact[n]*inv[m])%mod)*inv[n-m])%mod;
}
int main(){
fact[0]=inv[0]=1;
for(int i=1;i<=3000;i++){
    fact[i]=(i*fact[i-1])%mod;
    inv[i]=fp(fact[i],mod-2);
}
 ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
int n,k;
cin>>n>>k;
int r=n-k,b=k;
for(int i=1;i<=k;i++){
    if(r+1-i<0){cout<<0<<'\n';continue;}

    cout<<(ncr(b-1,i-1)*ncr(r+1,i))%mod<<'\n';
}
   return 0;
}


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

struct coordinate {
    int i;
    int j;
    int d;
    coordinate(int i, int j, int d) : i(i), j(j), d(d) { }
};

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

int main() {
    int H, W; cin >> H >> W;
    vector<string> s(H);
    
    int white = 0;
    REP(i, 0, H) {
        cin >> s[i];
        white += count(s[i].cbegin(), s[i].cend(), '.');
    }

    int d = 0;
    vector<vector<int>> seen(H, vector<int>(W, 0));
    queue<coordinate> q;
    q.push(coordinate(0, 0, 0));
    while (!q.empty() && d == 0) {
        auto now = q.front(); q.pop();
        REP(i, 0, 4) {
            int ni = now.i + dx[i];
            int nj = now.j + dy[i];
            if (ni < 0 || ni >= H || nj < 0 || nj >= W) continue;
            if (s[ni][nj] == '#' || seen[ni][nj] != 0) continue;
            q.push(coordinate(ni, nj, now.d + 1));
            seen[ni][nj] = 1;
            if (ni == H - 1 && nj == W - 1) {
                d = now.d + 1;
                break;
            }
        }
    }
    cout << ((d == 0) ? -1 : white - (d + 1)) << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a , b;
	scanf("%d%d",&a,&b);
	if(a==b)
	cout<<"Draw\n";
	else if(b==1)
	cout<<"Bob\n";
	else if(a==1)
	cout<<"Alice\n";
	else if(a>b)
	cout<<"Alice\n";
	else
	cout<<"Bob\n";
	
	
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
 
int main()
{
    int H, W, i, j; 
    while (1) {
        scanf("%d %d", &H, &W);
        if (H == 0 && W == 0) break;
        for (i = 0; i < H; i++) {
            for (j = 0; j < W; j++) {printf("#");}
            printf("\n");
        }
        printf("\n");
    }
    return 0;
}


Measured memory_bytes: 2000
// C++ 14
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(ll __x = __start; __x < __end; __x++)

set<int> S;
int n, k;
const int INF = 100000000;
vector<int> dp(10000000, -1);

int dfs(int m) {
  int &cc = dp[m];
  if (~cc) return cc;
  if (m >= n) return cc = m;
  int min_ = INF;
  loop(i,0,10) {
    if (S.count(i)) continue;
    if (m == 0 and i == 0) continue;
    min_ = min(min_, dfs(m * 10 + i));
  }
  return cc = min_;
}

int main() {
  cin >> n >> k;
  loop(i,0,k) {
    int a; cin >> a;
    S.insert(a);
  }
  cout << dfs(0) << endl;
  return 0;
}


Measured memory_bytes: 42132
def resolve():
    n, a, b = map(int, input().split())
    if b < a or (n == 1 and a != b):
        print(0)
    else:
        print((b * (n - 1) + a) - (a * (n - 1) + b) + 1)


if __name__ == "__main__":
    resolve()


Measured memory_bytes: 38384
use std::io::*;
use std::str::FromStr;

struct Scanner<R: Read> {
    reader: R,
}

#[allow(dead_code)]
impl<R: Read> Scanner<R> {
    fn new(reader: R) -> Scanner<R> {
        Scanner { reader: reader }
    }

    fn safe_read<T: FromStr>(&mut self) -> Option<T> {
        let token = self.reader.by_ref().bytes().map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        if token.is_empty() {
            None
        } else {
            token.parse::<T>().ok()
        }
    }

    fn read<T: FromStr>(&mut self) -> T {
        if let Some(s) = self.safe_read() {
            s
        } else {
            writeln!(stderr(), "Terminated with EOF").unwrap();
            std::process::exit(0);
        }
    }
}

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);

    loop {
        let n: u32 = sc.read();
        let x = sc.read();
        if n == 0 && x == 0 {
            break;
        }
        let mut cnt = 0;
        for i in 1..n+1 {
            for j in i+1..n+1 {
                for k in j+1..n+1 {
                    if i + j + k == x {
                        cnt += 1;
                    }
                }
            }
        }
        println!("{}", cnt);
    }
}



Measured memory_bytes: 5032
n, k = map(int, input().split())
arr = list(map(int, input().split()))

# dp初期化
dp = [float("inf")] * n
dp[0] = 0

for i in range(1, n):
    dp[i] = min(dp[j] + abs(arr[i] - arr[j]) for j in range(max(i - k, 0), i))

print(dp[n - 1])

Measured memory_bytes: 56416
// Package main provides
//
// File:  main.go
// Author: ymiyamoto
//
// Created on Sun Jan 27 15:07:05 2019
//
package main

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

type unionFind struct {
	roots  []int
	depths []int
}

func new(n int) unionFind {
	uf := unionFind{}
	uf.roots = make([]int, n+1)
	uf.depths = make([]int, n+1)

	for i := range uf.roots {
		uf.roots[i] = i
		uf.depths[i] = 0
	}

	return uf
}

func (uf unionFind) root(n int) int {
	parent := uf.roots[n]

	if parent == n {
		return n
	}
	root := uf.root(parent)
	uf.roots[n] = root
	return root
}

func (uf unionFind) union(n, m int) {
	rootN := uf.root(n)
	rootM := uf.root(m)
	if rootN < rootM {
		uf.roots[rootN] = rootM
	} else {
		uf.roots[rootM] = rootN
	}
}

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)
	N := nextInt()
	M := nextInt()

	arr := make([]int, N)
	for i := range arr {
		arr[i] = nextInt()
	}

	uf := new(N)
	for i := 0; i < M; i++ {
		n := nextInt()
		m := nextInt()
		uf.union(n, m)
	}

	m1 := map[int][]int{}
	m2 := map[int]map[int]bool{}
	for i := range arr {
		m1[uf.root(arr[i])] = append(m1[uf.root(arr[i])], i+1)
		if m2[uf.root(arr[i])] == nil {
			m2[uf.root(arr[i])] = map[int]bool{}
		}
		m2[uf.root(arr[i])][arr[i]] = true
	}

	ans := 0
	for k, v := range m1 {
		for i := range v {
			if _, ok := m2[k][v[i]]; ok {
				ans++
			}
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 31616