akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) (y<0||x<0||y>=h||x>=w)
#define dump(...)
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
#define INF (1001001001)
#define INFLL (1001001001001001001ll)
template<class T> ostream& operator << (ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v)) os<<*i<<(i==end(v)-1?"":" "); return os; }
template<class T> istream& operator >> (istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i; return is; }
template<class T> istream& operator >> (istream &is, pair<T,T> &p) {
    is>>p.first>>p.second; return is; }
template <class T> bool chmax(T &a,const T &b) {if(a<b) {a=b;return 1;} return 0;}
template <class T> bool chmin(T &a,const T &b) {if(b<a) {a=b;return 1;} return 0;}
template <class T> using heap = priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        #ifdef int
            #undef INF
            #define INF INFLL
            #define stoi stoll
        #endif
        cin.tie(0);ios::sync_with_stdio(false);
        cout<<setprecision(15)<<fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    string s;
    cin>>s;
    int n=SZ(s);
    string t=s;
    FORE(x,t) {
        if(x=='1') x='0';
        else if(x=='0') x='1';
    }

    auto check=[&](string u,int k) {
        int beg=-1;
        REP(i,n) {
            if(u[i]=='1') {
                if(beg==-1) beg=i;
            } else {
                if(beg!=-1) {
                    int l=i-beg;
                    if(k>beg && beg+l+k>n) {
                        return false;
                    }
                    beg=-1;
                }
            }
        }
        if(beg!=-1) {
            int l=n-beg;
            if(k>beg && beg+l+k>n) {
                return false;
            }
        }
        return true;
    };

    int L=1,R=n+1;
    while(R-L>1) {
        int M=(L+R)/2;
        if(check(s,M) || check(t,M)) {
            L=M;
        } else {
            R=M;
        }
    }
    cout<<L<<endl;
    return 0;
}


Measured memory_bytes: 720
//Problem B
#include<bits/stdc++.h>
using namespace std;
int rd(){
    int a=0;char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))a=(a<<1)+(a<<3)+(ch^48),ch=getchar();
    return a;
}
const int N=107;
int x,y,n,m,a[N],b[N],mx,mn;
#define WAR {printf("War");return 0;}
int main(){
    scanf("%d%d%d%d",&n,&m,&mx,&mn);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),mx=max(mx,a[i]);
    for(int i=1;i<=m;i++)scanf("%d",&b[i]),mn=min(mn,b[i]);
    if(mx+1>mn)WAR
    printf("No War");
    return 0;
}

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

int power(int x, int y) {
  if (y == 0) {
    return 1;
  }

  int ans = x;
  for (int i = 1; i < y; i++) {
    ans *= x;
  }
  return ans;
}

int main(int argc, char *argv[]) {

  int N, K;
  double dN, dK;
  double ans = 0;

  scanf("%d%d",&N, &K);
  dN = N;
  dK = K;

  for (int i = 1; i <= N; i++) {
    int omote = 0;
    int point = i;
    while(point < K) {
      omote += 1;
      point *= 2;
    }
    ans += (1 / (double)(N * power(2, omote)));
  }

  printf("%.12lf", ans);

}


Measured memory_bytes: 128
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;

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

// container util
#define all(x) (x).begin(), (x).end()

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

// typedef
typedef long long lint;
typedef unsigned long long ull;
typedef complex<long double> Complex;
typedef pair<int, int> P;
typedef tuple<int, int, int> TP;
typedef vector<int> vec;
typedef vector<vec> mat;

// constant
const int MOD = (int)1e9 + 7;
const int INF = (int)1e18;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

// 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();
}

//
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() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n;
  cin >> n;
  vector<int> a(n), tmp(n);
  rep(i, n) cin >> a[i], tmp[i] = a[i];

  sort(all(tmp));
  reverse(all(tmp));

  rep(i, n) {
    int j = 0;
    if (a[i] == tmp[j]) j++;
    cout << tmp[j] << endl;
  }

  return 0;
}

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

  ll sum=0;
  for(int i=1; i<=n; i++){
    if(i%3!=0 && i%5!=0) sum+=i; 
  }
  cout << sum << endl;
  return 0;
}

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

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

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

  vector<ll> suml(n, 0);
  suml[0] = a[0];
  for (int i = 1; i < n; i++) {
    suml[i] = suml[i - 1] + a[i];
  }

  ll total = suml[n - 1];

  ll ans = -1;
  for (int i = 0; i < n - 1; i++) {
    ll l = suml[i];
    ll r = total - suml[i];

    ll d = abs(l - r);

    if (ans == -1) {
      ans = d;
    } else {
      ans = min(ans, d);
    }
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3456
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
Author: z0marlin
Title: d.cpp
Time: 15-08-2019T13:48:02+0530 
I suck at CP T_T
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/
#include <bits/stdc++.h>
#if DEBUG
#define dprintf(...) printf(__VA_ARGS__)
#else
#define dprintf(...)
#endif
#define FOR(i, a, n) for(int i = a; i < n; ++i)
#define FORE(a, v) for(auto a:v)
#define MAX(a, b) ((a>b)?a:b)
#define MIN(a, b) ((a<b)?a:b)
#define MP(i, j) make_pair(i, j)
#define PB(a) push_back(a)
#define PPB(a) pop_back(a)
#define all(a) a.begin(), a.end()

using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<int,int> pii_t;
typedef pair<ll,ll> pll_t;
typedef vector<int> vi_t;
typedef vector<ll> vll_t;

const int MAX_SZ=1e6+2;
const int MOD=1e9+7;
int t = 1, n, m, q, ql, qr;
char ch;
string s;
vi_t cInd, res;
vi_t solve(){
    n=s.size();
	cInd.resize(n);
    res.resize(n);
    int lidx;
    for(int i=n-1; i>=0; i--){
        if(s[i]=='L') lidx=i;
        else cInd[i]=lidx;
    }
    FOR(i,0,n){
        if(s[i]=='R') lidx=i;
        else cInd[i]=lidx;
    }
    FOR(i,0,n){
        if(s[i]=='R'){
            if((cInd[i]-i)%2){
                res[cInd[i]-1]++;
            }
            else res[cInd[i]]++;
        }
        else{
            if((i-cInd[i])%2){
                res[cInd[i]+1]++;
            }
            else res[cInd[i]]++;
        }
    }
    return res;
}

int main(){
	// scanf("%d", &t);
	while(t--){
		cin>>s;
	}
    FORE(e, solve()){
        printf("%d ", e);
    }
    printf("\n");
}


Measured memory_bytes: 1792
//前置き
#pragma region

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<vector>
#include<list>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<queue>

using namespace std;

typedef  long long ll;

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

#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define SORT(a) sort(all(a))
#define REVERSE(a) reverse(all(a))

#define PRINT(str) printf(#str "\n")
#define yOUT PRINT(Yes)
#define nOUT PRINT(No)
#define YOUT PRINT(YES)
#define NOUT PRINT(NO)

#pragma endregion

//関数定義
#pragma region 
//偶数 ->　true :: 奇数　-> false
bool EVEN(ll a){
    return a%2-1;
}

//最大公約数
ll gcd(ll a, ll b) {  
    if (!b)  
        return a;  
    return gcd(b, a%b);  
}  

//最小公倍数
ll lcm(ll a, ll b) {  
    return a*b/gcd(a,b);  
} 

#pragma endregion


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

   int sum=0;

   int x,y;
   cin >> x ;
   if (n ==2){
       cout << x *2 <<endl;
       return 0;
   }
   sum +=x;

   REP(i,n-2){
       cin >> y;

       sum += min(x,y);
       x = y;
   }
   sum += y;

   cout << sum  <<endl;
}

    


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

using namespace std;

template<typename T>
struct BIT {
  vector<T> tree;

  BIT(int size) : tree(size + 1, 0) {};

  T sum(int a) {
    T res = 0;
    ++a;
    while (a) {
      res += tree[a];
      a -= a & -a;
    }
    return res;
  }

  T add(int a, int x) {
    ++a;
    while (a < tree.size()) {
      tree[a] += x;
      a += a & -a;
    }
  }
};

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

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, q;
  cin >> n >> q;

  BIT<int> bit(n);

  int t, x, y;
  rep(i, 0, q) {
    cin >> t >> x >> y;
    if (t == 0) bit.add(x - 1, y);
    else cout << bit.sum(y - 1) - bit.sum(x - 2) << endl;
  }
}


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

int main()
{
    string s;
    cin >> s;
    int cnt=0, ans=0;
    for(int i=0; i<3; ++i){
        if(s[i]=='R')++cnt;
        else cnt=0;
        ans=max(ans, cnt);
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 3624
import java.util.Scanner;

public class Main {

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

        String[] substr = str.split(" ", 0);

        int a = Integer.parseInt(substr[0]);
        int b = Integer.parseInt(substr[1]);

        String result = "";
        int n = 0;
        if (a >= b) {
        	result = substr[1];
        	n = a;
        } else {
        	result = substr[0];
        	n = b;
        }
    	StringBuilder buff = new StringBuilder();
        for (int i=0; i<n; i++) {
        	buff.append(result);
        }
        System.out.println(buff.toString());

        scan.close();

    }

}

Measured memory_bytes: 23124
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include<cmath>
using namespace std;
#define rep(n) for (int i = 0; i < (n); ++i)
typedef long long ll;
double distance(double xi,double xj,double yi,double yj){
    double x = xi-xj;
    double y = yi-yj;
    return sqrt(x*x+y*y);
}
int kaijyo(int n){
    if(n==1) return 1;
    else return n*kaijyo(n-1);
}
int main()
{
    int n;
    cin >> n;
    vector<double> x(n);
    vector<double> y(n);
    rep(n){
        cin>>x[i]>>y[i];
    }
    double sum=0;
    for(int i=0;i<n;++i){
        for(int j=i;j<n;++j){
            sum+=distance(x[i],x[j],y[i],y[j]);
        }
    }
    printf("%.10f\n",2*sum/n);
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#define int long long
#define mod 1000000007
#define for0(i, n) for(int i = 0; i < (n); i++)
#define for1(i, n) for(int i = 1; i <= (n);i++)
#define mp make_pair
using namespace std;
int a, b, c, d, n, ans;
int ar[234567];
string s;
bool b1, b2;
signed main() {
	cin >> n;
	for1(i, n) {
		cin >> s;
		if (s == "E869120")ans++;
	}cout << ans << endl;
}


Measured memory_bytes: 3212
/*
 * Author: .-O_O-.
 */
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include<bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define pb push_back
#define vi vector<int>
#define rep0(a,b) for(int a=0;a<b;a++)
#define rep1(a,b) for(int a=1;a<=b;a++)
#define repp(a,b,c) for(int a=b;a<c;a++)
#define in insert
#define len length()
#define si size()
#define lb lower_bound
#define ub upper_bound
#define beg begin()
#define en end()
#define f first
#define s second
#define pr(a) cout<<a
#define pr2(a,b) cout<<a<<" "<<b<<"\n"
#define nx cout<<"\n"
#define int long long
// void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
                                                     
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]"<<endl;}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define deb(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define deb(x...)
#endif
const ll mod = 1000000007;
const ll N = 105;
const ll mm = 1e+18;
void solve()
{
    int n;
    cin>>n;
    int l=1;
    int r=2e9+10;
    int ans=0;
    while(l<r){
        int mid=(l+r)>>1;
        if((mid*(mid+1))/2>=n){
            ans=mid;
            r=mid;
        }
        else l=mid+1;
    }
    pr(ans);
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    rep1(_i,t){
        //cout<<"Case #"<<_i<<": ";
        solve();
        //nx;
    }
    return 0;
}

Measured memory_bytes: 3644
import math

def is_prime(n):
    if n <= 1:
        return False

    if n % 2 == 0 and n > 2:
        return False
    
    for i in range(2, math.floor(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

N = int(input())
ans = 0
for _ in range(N):
    n = int(input())
    if is_prime(n):
        ans += 1
print(ans)


Measured memory_bytes: 5680
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>
#include <sstream>
#include <istream>

using namespace std;

typedef long long ll;
typedef pair<ll, int> P;

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

	int sum = 0;
	for(int i=1;i<=n;i++){
		sum += i+l-1;
	}

	int ans = 200000;
	int m = 200000;
	for(int i=1;i<=n;i++){
		if(m>abs(i+l-1)){
			m = abs(i+l-1);
			ans = sum-(i+l-1);
		}
	}
	cout << ans << endl;
	
	return 0;
}

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

#define endl "\n"
#define x first
#define y second
#define debug(x) cerr << #x << ": " << x << endl;
#define all(x) x.begin(), x.end()

typedef long long LL;
typedef pair <LL, LL> PLL;

const LL maxn = 1000010;
const LL mod = 1000000007;
const LL inf64 = 1LL<<60;

vector <bool> is_prime(maxn, true);

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

    for (LL i = 2; i*i < maxn; i++)
        if (is_prime[i]) for (LL j = i*i; j < maxn; j += i)
            is_prime[j] = false;

    LL n, p;
    cin >> n >> p;

    map <LL, LL> cnt;
    for (LL i = 2; i < maxn; i++)
        if (is_prime[i]) {
            while (p % i == 0)
                p /= i, cnt[i]++;
    }
    if (p != 1) cnt[p]++;

    LL ans = 1;
    for (auto p : cnt) {
        for (LL i = 0; i < p.y/n; i++)
            ans *= p.x;
    }

    cout << ans << endl;

    return 0;
}

// hello!

Measured memory_bytes: 384
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
  return int(readline())
w,h,x,y = readInts()
w = float(w)
h = float(h)
area = (w*h)/2 # 一意
#print(w,h)
result = 0
if (x+x) == w and (y+y) == h:
    # 中心で分割できるか
    result = 1
print(area,result)


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

const int MAX = 1000010;
 const int MOD = 1000000007;
 
 long long fac[MAX], finv[MAX], inv[MAX];
 
 // テーブルを作る前処理
 void COMinit() {
     fac[0] = fac[1] = 1;
     finv[0] = finv[1] = 1;
     inv[1] = 1;
     for (int i = 2; i < MAX; i++){
         fac[i] = fac[i - 1] * i % MOD;
         inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
         finv[i] = finv[i - 1] * inv[i] % MOD;
     }
 }
 
 // 二項係数計算
 long long COM(int n, int k){
     if (n < k) return 0;
     if (n < 0 || k < 0) return 0;
     return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
 }
int main() {
    ll x,y;
    std::cin >> x>>y;
    ll mod = 1000000007;
    COMinit();
    ll res = 0;
    if((x+y)%3!=0){
        std::cout << 0 << std::endl;
        return 0;
    }
    for (int i = 0; i <= (x+y)/3; i++) {
        ll j = (x+y)/3-i;
        if(i%2!=x%2 || ((x+y)/3-i)%2!=y%2){
            continue;
        }
        
        if((i+2*j)==x && (i*2+j)==y){
            res += COM((x+y)/3,i)%mod;
            res %= mod;
        }
    }

    std::cout << res << std::endl;
}


Measured memory_bytes: 23680
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.TreeMap;


public class Main {
	static long[][] memo;

	public static long dp2(int[] weights, long[] values, int i, int N, int W, int curW) {
		if(i>=N || curW>W)
			return 0;
		long take;
		long leave;
		if(memo[curW][i]!=-1)
			return memo[curW][i];
		else {
			take = values[i]+dp2(weights,values,i+1,N,W,curW+weights[i]);
			leave = dp2(weights,values,i+1,N,W,curW);
		}
		if(weights[i]+curW>W)
			take = -1;
		return memo[curW][i] = (take>leave)?take:leave;
		
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int W = Integer.parseInt(st.nextToken());
		int w;
		long v;
		memo = new long[W+1][N];
		for (long[] i : memo) {
			Arrays.fill(i, -1);
		}
		int[] weights = new int[N];
		long[] values = new long[N];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			w = Integer.parseInt(st.nextToken());
			v = Long.parseLong(st.nextToken());
			weights[i] = w;
			values[i] = v;
		}
//		System.out.println(dp(weights, values, 0, N, W).getValue());
		System.out.println(dp2(weights, values, 0, N, W,0));
	}

}


Measured memory_bytes: 127820
#include<iostream>
// Need start
#include<vector>
#include<limits>
// Need end
using namespace std;
typedef long long ll;

template <class T>
class Bellmanford {
    private:
        T inf;
        struct edge {
            T from, to, cost;
        };
        vector<edge> es;
        vector<T> dist;
        vector<T> is_negative;
        T node_num, edge_num;
        bool negative_loop;
    public:
        Bellmanford(T v, T e) {
            inf = numeric_limits<T>::max();  // please set yourself
            node_num = v;
            edge_num = e;
            dist.resize(node_num);
            is_negative.resize(node_num);
            negative_loop = false;
            fill(dist.begin(), dist.end(), inf);
            fill(is_negative.begin(), is_negative.end(), false);
        }
        void add_edge(T from, T to, T cost) {
            edge e = {from, to, cost};
            es.push_back(e);
        }
        void calc_shortest_path(T start) {
            dist[start] = 0;
            for (T i = 0; i < node_num; i++) {
                for (T j = 0; j < edge_num; j++) {
                    edge e = es[j];
                    if (dist[e.from] != inf && dist[e.to] > dist[e.from] + e.cost) {
                        dist[e.to] = dist[e.from] + e.cost;
                        if (i == node_num - 1) {
                            negative_loop = true;
                            is_negative[e.to] = true;
                        }
                    }
                }
            }
        }
        bool is_negative_loop() {
            return negative_loop;
        }
        bool have_negative_path(T u) {
            return is_negative[u];
        }
        T get_dist(T u) {
            return dist[u];
        }
};

int main() {
    ll N, M;
    cin >> N >> M;
    ll a, b, c;
    Bellmanford<ll> B(N, M);
    for (int i = 0; i < M; i++) {
        cin >> a >> b >> c;
        a--, b--;
        B.add_edge(a, b, -c);
    }
    B.calc_shortest_path(0);
    ll ans = -B.get_dist(N - 1);
    if (B.is_negative_loop() && B.have_negative_path(N - 1)) {
        cout << "inf" << endl;
    }
    else {
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<ll, ll>;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;
#ifdef DEBUG_ 
#include "../program_contest_library/memo/dump.hpp"
#else
#define dump(...)
#endif
const ll INF = 1LL<<60;

void dfs(ll pos, ll num) {

}

int main(void) {
    ll n, m;
    cin >> n >> m;
    bool flag = true;
    vector<ll> digit(n, -1);
    REP(i, m) {
        ll s, c;
        cin >> s >> c;
        s--;
        if(digit[s] != -1 && c != digit[s]) {
            flag = false;
        }
        digit[s] = c;
    }
    if(!flag) {
        cout << -1 << endl;
        return 0;
    }

    if(n == 1) {
        if(digit[0] == -1) digit[0] = 0;
        cout << digit[0] << endl;
        return 0;
    }

    if(digit[0] == 0) {
        cout << -1 << endl;
        return 0;
    }

    if(digit[0] == -1) digit[0] = 1;
    FOR(i, 1, n) if(digit[i] == -1) digit[i] = 0;
    REP(i, n) cout << digit[i];
    cout << endl;

    return 0;
}

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

int main(){
  ll a,b,x,ans;
  cin >> a >> b >> x;
  if(a == 0){
    ans = b/x + 1;
  }
  else ans = b/x - (a-1)/x;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<P1,ll> P2;
const ll INF=1000000000000000001;
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};


int main() {

	ll x,y;

	cin>>x>>y;

	ll o=x;
	ll total=1;
	for(ll i=x; i<y+1; i++){
		if(o*2<=y){
			total++;
			o=o*2;
		}else{
			break;
		}
	}
	cout<<total<<endl;

	return 0;
}


Measured memory_bytes: 256
//agrawal117
//chahatagrawal117
#include<bits/stdc++.h>
#define endl '\n'
#define mod 1000000007
typedef long long int ll;
using namespace std;
#define MAX 100005
vector<ll> v[4];
int idx(char a, char b)
{
    if(b=='R') swap(a,b);
    if(a=='R' && b=='G') return 3;
    if(a=='R' && b=='B') return 2;
    else return 1;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n; cin>>n;
    string s; cin>>s;
    
    for(int i=0;i<s.size();i++){
        if(s[i]=='R') v[1].push_back(i);
        else if(s[i]=='G') v[2].push_back(i);
        else v[3].push_back(i);
    }
    ll ans=0;
    for(int j=1;j<s.size()-1;j++){
        for(int i=0;i<j;i++){
            if(s[j]!=s[i]){
                int kk=idx(s[i],s[j]);
                int k=lower_bound(v[kk].begin(),v[kk].end(),j)-v[kk].begin();
                ans+=(v[kk].size()-k);
                 k=lower_bound(v[kk].begin(),v[kk].end(),2*j -i)-v[kk].begin();
                 if( k!=v[kk].size() && v[kk][k]==(2*j)-i) ans--;
            }
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3692
import java.io.*;
import java.util.*;

class Main {

    public static void main(String[] args) {
        MyScanner sc = new MyScanner();
        int N = sc.nextInt();
        int[] B = new int[N];

        for (int i=0; i<N-1; i++){
            B[i] = sc.nextInt();
        }
    
        int ans = B[0] + B[N-2];
        for (int i=0; i<N-1; i++){
            ans += Math.min(B[i], B[i+1]);
        }
        System.out.println(ans);

    }

    static class MyScanner {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 1 << 15);
        StringTokenizer tokenizer;
    
        String next() {
            try {
                while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                    tokenizer = new StringTokenizer(reader.readLine());
                }
            } catch (IOException ignored) {
            }
            return tokenizer.nextToken();
        }
    
        int nextInt() {
            return Integer.parseInt(next());
        }
    
        long nextLong() {
            return Long.parseLong(next());
        }
    }
}

Measured memory_bytes: 21204
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;
using P = pair<int, int>;
constexpr ld EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr int MOD = 998244353;

template <typename T>
void printv(const vector<T> &v)
{
    int sz = v.size();
    for (int i = 0; i < sz; i++)
    {
        cout << v[i] << " \n"[i == sz - 1];
    }
}

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

    string s;
    cin >> s;
    int n = s.length();
    vector<vector<ll>> dp(2 * n + 1, vector<ll>(2 * n + 1, 0));
    dp[0][0] = 1;
    vector<vector<ll>> sum(n + 1, vector<ll>(2, 0));
    s = "$" + s;
    for (int i = 1; i <= n; i++)
    {
        sum[i][0] = sum[i - 1][0];
        sum[i][1] = sum[i - 1][1];
        if (s[i] == '0')
        {
            sum[i][0] += 2;
        }
        else if (s[i] == '1')
        {
            sum[i][0]++;
            sum[i][1]++;
        }
        else
        {
            sum[i][1] += 2;
        }
    }
    // i := 赤の個数
    // j := 青の個数
    for (int i = 0; i <= 2 * n; i++)
    {
        for (int j = 0; j <= 2 * n; j++)
        {
            int turn = min(i + j, n);
            bool red = (sum[turn][0] >= i) && (i > 0);
            bool blue = (sum[turn][1] >= j) && (j > 0);
            if (red)
            {
                dp[i][j] += dp[i - 1][j];
                dp[i][j] %= MOD;
            }
            if (blue)
            {
                dp[i][j] += dp[i][j - 1];
                dp[i][j] %= MOD;
            }
        }
    }
    cout << dp[sum[n][0]][sum[n][1]] << endl;
}


Measured memory_bytes: 125568
lines = []
while line = gets
    lines << line.chomp.split(' ').map(&:to_i)
end

D = lines[0][0]
Inf = 10 ** 10

last_date = []
for i in 1..26 do
  last_date.push(0)
end

for i in 1..D do
  max_satis = - Inf
  best_contest = 0
  for k in 1..26 do
    now_satis = 0
    now_satis += lines[i+1][k-1]
    now_satis += lines[1][k-1] * (i - last_date[k-1])
    if now_satis > max_satis then
      if i == D or lines[i+1][k-1] > lines[i+2][k-1] then
        max_satis = now_satis
        best_contest = k
      end
    end
  end
  last_date[best_contest-1] = i
  if i < D then
    puts best_contest
  else
    print best_contest
  end
end

Measured memory_bytes: 14372
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    A, B, K = map(int, readline().split())
    if K <= A:
        print(A - K, B)
    elif K <= A + B:
        print(0, A + B - K)
    else:
        print(0, 0)

    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int main()
{
    int n;
    cin >> n;
    int arr[n + 1];
    int sum = 0;
    for(int i = 0; i < n; i++)
    {
        cin >> arr[i];
        sum += arr[i];
    }
    int target = round(1.0 * sum / n);
    int cost1 = 0;
    for(int i = 0; i < n; i++)
        cost1 += (arr[i] - target) * (arr[i] - target);
    cout << cost1;
    return 0;
}

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

### TESTCASE
test = ""
#test = \
"""
3 1
4 1 5
ans 5
"""

"""
8 9
7 9 3 2 3 8 4 6
ans 0
"""

"""
3 0
1000000000 1000000000 1000000000
ans 3000000000
"""
############
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
####### MAIN

n, k = map(int, input2().split())
h = list(map(int, input2().split()))

sorth = sorted(h)

for i in range(min(n, k)):
    sorth.pop()

print(sum(sorth))



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

using namespace std;
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}

int main(){
  int N;
  cin >> N;
  string s = "";
  if(N == 0){
    cout << 0 << endl;
    return 0;
  }
  while(N != 0){
    if( N % (-2) == 0) s = s + "0";
    else if(N % (-2) == 1) s = s + "1";
    else{
      N = N - 2;
      s = s + "1";
    }

    N /= (-2);
  }
  reverse(s.begin(), s.end());
  cout << s << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define PB push_back
#define MP make_pair
#define MOD 1000000007LL
#define endl "\n"
const ll UNDEF = -1;
template<typename T> inline bool chkmax(T &aa, T bb) { return aa < bb ? aa = bb, true : false; }
template<typename T> inline bool chkmin(T &aa, T bb) { return aa > bb ? aa = bb, true : false; }
ll a[2000];
int main() {
	ios_base::sync_with_stdio(false);
	ll n; cin>>n;
	n=2*n;
	for (ll i=0;i<n;i++) {
		cin>>a[i];
	}
	sort(a,a+n);
	ll ans=0;
	for (ll i=0;i<n;i+=2) {
		ans+=a[i];
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
package main

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

type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

func main() {
	sc := NewScanner()
	N := sc.nextInt()
	A, B, C := sc.nextIntSlice(N), sc.nextIntSlice(N), sc.nextIntSlice(N)
	sort.Sort(sort.Reverse(sort.IntSlice(A)))
	sort.Ints(C)
	count := 0
	for i := 0; i < N; i++ {
		upper := sort.Search(N, func(index int) bool {
			return A[index] < B[i]
		})
		countA := N - upper
		lower := sort.Search(N, func(index int) bool {
			return C[index] > B[i]
		})
		countC := N - lower
		count += countA * countC
	}
	fmt.Println(count)
}


Measured memory_bytes: 5504
def resolve():
    N = int(input())
    S = list(input())
    nopen = 0
    addleft = 0
    addright = 0
    for s in S:
        if s == "(":
            nopen += 1
        else:
            if nopen == 0:
                addleft += 1
            else:
                nopen -= 1
    addright = nopen
    print("("*addleft+"".join(S)+")"*addright)


if __name__ == '__main__':
    resolve()

Measured memory_bytes: 3060
#include<bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
using LL = long long;
const LL LINF = 1e18;
using namespace std;
#define COUT(v) cout<<(v)<<endl
#define CIN(n)  int(n);cin >> (n)
#define SCIN(n) string(n);cin >> (n)
#define YES(n) cout<<((n)? "YES" : "NO")<<endl
#define Yes(n) cout<<((n)? "Yes" : "No")<<endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) <<endl

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

#define FOREACH(x,a) for(auto& (x) : (a) )

#define ALL(obj) (obj).begin(),(obj).end()

#define P pair<int,int>
#define I vector<int>
#define S set<int>
#define pb(v) push_back(v)
#define V vector
#define rt return
#define rmsame(a) sort(ALL(a)),a.erase(unique(ALL(a)), a.end())
class Edge{
public:
    int from,to,value;
    Edge(int a,int b,int c){
        from = a;
        to = b;
        value = c;
    }
    Edge(int a,int b){
        from = a;
        to = b;
    }
};


int main(){
    CIN(A);CIN(B);CIN(C);
    S s;
    s.insert(A);s.insert(B);s.insert(C);
    COUT(s.size());
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <math.h>
using namespace std;

int main()
{
    int n,m,l;
    cin >> n >> m >> l;

    // new
    int** mata = new int*[n];
    long long int** matc = new long long int*[n];
    for(int i = 0; i < n; i++)
    {
        mata[i] = new int[m];
        matc[i] = new long long[l];
    }
    int** matb = new int*[m];
    for(int i = 0; i < m; i++)
    {
        matb[i] = new int[l];
    }

    // in
    for(int i = 0; i<n;i++)
    {
        for(int j = 0; j < m;j++)
        {
            cin >> mata[i][j];
        }       
    }
    for(int i = 0; i<m;i++)
    {
        for(int j = 0; j < l;j++)
        {
            cin >> matb[i][j];
        }       
    }

    // calc"C"
    for(int i = 0; i < n;i++)
    {
        for(int j = 0; j < l;j++)
        {
            matc[i][j] = 0;
            for(int k = 0; k < m;k++)
            {
                matc[i][j] += mata[i][k] * matb[k][j];
            }
            if(j == 0) cout << matc[i][j];
            else cout << " " << matc[i][j];
        }
        cout << endl;       
    }

    // del
    for(int i = 0; i < n; i++)
    {
        delete[] mata[i];
        delete[] matc[i];
    }
    for(int i = 0; i < m; i++)
    {
        delete[] matb[i];
    }
    delete[] mata;
    delete[] matb;
    delete[] matc;

    return 0;
}






Measured memory_bytes: 3224
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, x = 0, ans = 0;
    char s[105];
    scanf("%d%s", &n, s);
    for (int i = 0; i < n; i++) {
        if ('D' == s[i]) {
            x--;
        } else if ('I' == s[i]) {
            x++;
            ans = max(ans, x);
        }
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long int
#define ordered_set tree < ll ,  null_type ,  less<ll> ,  rb_tree_tag ,  tree_order_statistics_node_update >
//added two more functions to set
//(1)*(set.find_by_order(k))[kth element in the sorted set] 
//(2)set.order_of_key(k)[count of elements strictly less than k]
typedef vector< int > vi;
typedef vector< ll > lvi;
typedef vector< vi > vvi;
typedef vector< lvi > lvvi;
typedef pair< int,int > ii;
typedef pair< ll,ll > lii;
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(auto i = (c).begin(); i != (c).end(); i++)//remember i is an iterator
#define present(c,x) ((c).find(x) != (c).end())//for sets,maps,multimaps
#define cpresent(c,x) (find(all(c),x) != (c).end())//for vectors
#define tc(t) int (t); cin>>(t);while((t)--)
#define ff first
#define ss second
#define mp make_pair
#define ld long double
#define ull unsigned long long int
#define mod 1000000007
ll h,w,k;
string s[30];
int recurs(int x,int r)// r is number of rows
{
	vi v(r);
	int sum1=0;
	sum1=s[0][0]-'0';
	int m=0,rval=0;
	for(int i=0;i<h-1;i++)
	{
		if((x&(1<<i))!=0)
		{
			if(sum1>k) return 1e6;
			v[m]=sum1;
			m++;
			sum1=(s[i+1][0]-'0');
		}	
		else
		{
			sum1+=(s[i+1][0]-'0');
		}
	}
	// cout<<"m: "<<m<<endl;
	if(sum1>k) return 1e6;
	v[m]=sum1;
	// cout<<v[0]<<endl;
	// cout<<v[m]<<" "<<endl;
	for(int i=1;i<w;i++)
	{
		vi v1(r);
		m=0;
		sum1=s[0][i]-'0';
		for(int j=0;j<h-1;j++)
		{
			if((x&(1<<j))!=0)
			{
				if(sum1>k) return 1e6;
				v1[m]=sum1;
				m++;
				sum1=(s[j+1][i]-'0');
			}	
			else
			{
				sum1+=(s[j+1][i]-'0');
			}
		}
		if(sum1>k) return 1e6;
		v1[m]+=sum1;
		int flag=0;
		for(int j=0;j<=m;j++)
		{
			v[j]+=v1[j];
			if(v[j]>k) flag=1;
			// cout<<v[j]<<" ";
		}
		// cout<<endl;
		if(flag==1)
		{
			// cout<<i<<endl;
			rval++;
			v=v1;
		}
	}
	// cout<<rval<<"***"<<endl;
	return rval;
}
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);	
	cin>>h>>w>>k;
	for(int i=0;i<h;i++)
	{
		cin>>s[i];
	}
	int ans=1e6;
	for(int i=0;i<(1<<(h-1));i++)
	{
		int tmp=0;
		for(int j=0;j<(h-1);j++)
		{
			if((i&(1<<j))!=0) tmp++;
		}
		// cout<<i<<" "<<tmp<<" ";
		tmp+=recurs(i,tmp+1);
		// cout<<tmp<<endl;
		// cout<<"#########\n";
		ans=min(ans,tmp);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define int long long

typedef struct {
	int N;
	int *u;
	int *u_rank;
}union_find;

union_find *make_union_find(int N){
	int i;
	union_find *uf = (union_find *)malloc(sizeof(union_find));
	uf->N = N;
	uf->u = (int *)malloc(sizeof(int) * N);
	uf->u_rank = (int *)malloc(sizeof(int) * N);
	for(i = 0; i < N; i++){
		(uf->u)[i] = i;
		(uf->u_rank)[i] = 1;
	}
	return uf;
}

int root_uf(int x, union_find *uf){
	int *u = uf->u;
	if(u[x] == x){
		return x;
	}
	else{
		u[x] = root_uf(u[x], uf);
		return u[x];
	}
}

void combine_uf(int x, int y, union_find *uf){
	int x_root = root_uf(x, uf);
	int y_root = root_uf(y, uf);
	int *u = uf->u;
	int *u_rank = uf->u_rank;
	if(x_root == y_root){
		return;
	}
	else if(u_rank[x_root] < u_rank[y_root]){
		u[x_root] = y_root;
		u_rank[y_root] += u_rank[x_root];
		u_rank[x_root] = 0;
	}
	else{
		u[y_root] = x_root;
		u_rank[x_root] += u_rank[y_root];
		u_rank[y_root] = 0;
	}
}

//xとyが同じ集合に属していれば1を,そうでなければ0を返す
int is_same_union_uf(int x, int y, union_find *uf){
	if(root_uf(x, uf) == root_uf(y, uf)){
		return 1;
	}
	else{
		return 0;
	}
}

//xが属する集合の要素数を返す
int rank_uf(int x, union_find *uf){
	return (uf->u_rank)[root_uf(x, uf)];
}

typedef struct {
	int a;
	int b;
	int w;
}edge;

signed compair_edge(const void *x, const void *y){
	return ((edge *)x)->w - ((edge *)y)->w;
}

signed main(){
	int N, M, K, i;
	scanf("%lld%lld%lld", &N, &M, &K);
	int *c = (int *)malloc(sizeof(int) * N);
	for(i = 0; i < N; i++){
		scanf("%lld", &c[i]);
		c[i]--;
	}
	edge *es = (edge *)malloc(sizeof(edge) * M);
	for(i = 0; i < M; i++){
		scanf("%lld%lld%lld", &es[i].a, &es[i].b, &es[i].w);
		es[i].a--;
		es[i].b--;
	}
	qsort(es, M, sizeof(edge), compair_edge);
	union_find *uf = make_union_find(N);
	int *prev = (int *)malloc(sizeof(int) * K);
	for(i = 0; i < K; i++){
		prev[i] = -1;
	}
	for(i = 0; i < N; i++){
		if(c[i] >= 0){
			if(prev[c[i]] >= 0){
				combine_uf(i, prev[c[i]], uf);
			}
			prev[c[i]] = i;
		}
	}
	int ea, eb, now = 0, ans = 0;
	for(i = 0; i < M && now < K - 1; i++){
		ea = es[i].a;
		eb = es[i].b;
		if(is_same_union_uf(ea, eb, uf) == 0){
			combine_uf(ea, eb, uf);
			ans += es[i].w;
			now++;
		}
	}
	if(now == K - 1){
		printf("%lld\n", ans);
	}
	else{
		printf("-1\n");
	}
	return 0;
}

Measured memory_bytes: 5628
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) FOR(i,0,n)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
const ll INF = (1ll << 60);

int main() {
  ll N,W; cin>>N>>W;
  vi v(N),w(N);
  REP(i,N) cin>>v[i]>>w[i];
  vvi dp(N,vi(W+1));
  REP(j,W+1) if(w[0]==j) dp[0][j]=v[0];
  FOR(i,1,N) REP(j,W+1){
    if(j>=w[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
    else dp[i][j]=dp[i-1][j];
  }
  ll ans=0; REP(i,W+1) ans=max(ans,dp[N-1][i]);
  cout<<ans<<endl;
}

Measured memory_bytes: 10744
for e in iter(input,'0 0'):
    a,b=map(int,e.split())
    m=[[0]*-~b for _ in[0]*-~a]
    m[1][1]=1
    for _ in[0]*int(input()):
        i,j=map(int,input().split())
        m[i][j]=-1
    for k in range(3,a+b+1):
        for l in range(1,k):
            if l<=a and k-l<=b and m[l][k-l]>=0:
             s,t=m[l-1][k-l],m[l][k-l-1]
             m[l][k-l]=s*(s>0)+t*(t>0)
    print(m[a][b])


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

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

	vector<int> dp(n + 1);
	vector<int> h(n + 1);
	h[0] = 0;
	for (int i = 1; i < n+1; i++) {
		cin >> h[i];
	}
	dp[1] = 0;
	for (int i = 2; i < n + 1; i++) {
		if (i - 2 >= 1) {
			dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]), dp[i - 2] + abs(h[i - 2] - h[i]));
		}
		else {
			dp[i] = dp[i - 1] + abs(h[i - 1] - h[i]);
		}
	}
	int ans = dp[n];
	cout << ans << endl;
}

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

int main() {
	int N; cin >> N;
	map<int, int> mpe, mpo;
	for (int i = 0; i < N; i++) {
		int a; cin >> a;
		if (i & 1) mpo[a]++;
		else mpe[a]++;
	}
	int e = 0, o = 0, ev, ov;
	for (auto &u: mpe) {
		if (e < u.second) {
			e = u.second;
			ev = u.first;
		}
	}
	for (auto &u : mpo) {
		if (o < u.second) {
			o = u.second;
			ov = u.first;
		}
	}
	mpe.erase(ev);
	mpo.erase(ov);
	int e2 = 0, o2 = 0;
	for (auto &u : mpe)
		if (e2 < u.second) e2 = u.second;
	for (auto &u : mpo)
		if (o2 < u.second) o2 = u.second;
	int ans = 0;
	if (ev != ov) ans = N - e - o;
	else ans = min(N - e2 - o, N - e - o2);
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 4992
/**************************
*                         *
*  Nothing Is Impossible  *
*                         *
**************************/
#include <algorithm>
#include <iostream>
#include <fstream>
#include <ctype.h>
#include <string>
#include <vector>
#include <thread>
#include <math.h>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <set>
#include <map>
#define GetRand(Min, Max) ((rand()%(int)(((Max) + 1)-(Min))) + (Min))
#define Rep(i, min, max) for(int i = min; i < max; ++i)
#define PB push_back
#define MP make_pair
typedef long long ll;
typedef long double ld;
using namespace std;

void Solve(){
	string s,t;	cin >> s >> t;
	int ans = 100000;
	Rep(i,0,(int)s.size()-(int)t.size()+1){
		int ind = 0;
		int best = 0;
		Rep(j,i,i+(int)t.size()){
			if(s[j] != t[ind]){
				best++;
			}
			ind++;
		}
		ans = min(ans,best);
	}
	cout << ans << endl;
}

int main(){
	ios::sync_with_stdio(NULL);
	cin.tie(NULL); cout.tie(NULL);
	int t = 1;
	//int t;	cin >> t;
	while(t--) Solve();
	return 0;
}



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

int main(){
	int N;
	cin>>N;
	int A[2][N];
	for(int i=0;i<2;++i){
		for(int j=0;j<N;++j){
			cin>>A[i][j];
		}
	}
	/*
	for(int i=0;i<2;++i){
		for(int j=0;j<N;++j){
			cout<<A[i][j]<<" ";
		}
		cout<<endl;
	}
	*/
	int ans=0;
	ans+=A[0][0];
	for(int i=0;i<N;++i){
		ans+=A[1][i];
	}

	int tmp=ans;
	for(int i=1;i<N;++i){
		tmp+=A[0][i]-A[1][i-1];
		if(tmp>ans)ans=tmp;
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 256
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def solve(N,M,p1,p2):
    ans = 0

    for i in range(N):
        left = k - p1[i]

        lo = 0
        hi = M - 1

        temp = (i + 1)

        if (left >= 0):
            while (lo <= hi):
                # print(lo, hi, ans)
                mid = (lo + hi) // 2

                if (p2[mid] > left):
                    hi = mid - 1
                else:
                    lo = mid + 1
                    ans = max(ans, temp + lo)
            ans = max(ans, temp + lo)


    return ans


n,m,k = MAP()

a = LIST()

b = LIST()

prefA = [0]*n
prefA[0] = a[0]

for i in range(1, n):
    prefA[i] = prefA[i-1] + a[i]


pref = [0]*m

pref[0] = b[0]

for i in range(1, m):
    pref[i] = pref[i-1] + b[i]
#
# print(prefA)
# print(pref)

print(max(solve(n,m,prefA,pref), solve(m,n,pref,prefA)))

Measured memory_bytes: 111124
en=[chr(i) for i in range(65,91)]+list(' .,-\'?')
de={
'101':' ','000000':'\'','000011':',','10010001':'-','010001':'.','000001':'?',
'100101':'A','10011010':'B','0101':'C','0001':'D','110':'E','01001':'F',
'10011011':'G','010000':'H','0111':'I','10011000':'J','0110':'K','00100':'L',
'10011001':'M','10011110':'N','00101':'O','111':'P','10011111':'Q','1000':'R',
'00110':'S','00111':'T','10011100':'U','10011101':'V','000010':'W','10010010':'X',
'10010011':'Y','10010000':'Z'
}
while 1:
    try:s=input()
    except:break
    a=b=''
    for x in s:a+=str(bin(en.index(x)))[2:].zfill(5)
    for i in range(len(a)):
        b+=a[i]
        if b in de:print(de[b],end='');b=''
    print()

Measured memory_bytes: 7464
#include <iostream>
#define ll long long
using namespace std;

int main(){
  int n; cin >> n;
  ll march[5]; for(int i=0; i<5; i++){march[i]=0;}
  
  string name;
  for(int i=0; i<n; i++){
    cin >> name;
    if('M'==name[0]){march[0]++;}
    if('A'==name[0]){march[1]++;}
    if('R'==name[0]){march[2]++;}
    if('C'==name[0]){march[3]++;}
    if('H'==name[0]){march[4]++;}
  }
  
  ll sum=0;
  for(int i=0; i<3; i++){
    for(int j=i+1; j<4; j++){
      for(int k=j+1; k<5; k++){
      	sum = sum + march[i]*march[j]*march[k];
      }
    }
  }
  
  cout << sum;
  
  return 0;
}

Measured memory_bytes: 256