akhauriyash/Code-Regression huggingface dataset:
/******************************************
* AUTHOR : RAJAGOPALAN *
* NICK : ARNO *
* INSTITUTION : VIT *
******************************************/
// #include <bits/stdc++.h>
// #define ll long long
// #define ull unsigned long long
// #define pb push_back
// #define mp make_pair
// #define all(x) (x).begin(),(x).end()
// #define alli(a, n, k) (a+k),(a+n+k)
// #define FP(i, a, b, k) for(__typeof(a) i = a;i < b;i += k)
// #define FS(i, a, b, k) for(__typeof(a) i = a;i > b;i -= k)
// #define IT(it, a) for(__typeof(a.begin()) it = a.begin();it != a.end(); ++it)

// #define eps 1e-6
// #define pi 3.141592653589793
// using namespace std;

// template<class T> inline T gcd(T x, T y) { if (!y) return x; return gcd(y, x%y);}
// typedef vector<int> VII;
// typedef vector<ll> VLL;
// typedef pair<int, int> PII;
// typedef vector< pair<int, int> > VPII;
// typedef vector< pair<int, PII > > VPPI;
// const int MOD = 1e9 + 7;
// const int INF = 1e9;
// ll fastpower(ll x,ll y)
// {
//     ll res=1;
//     while(y>0)
//     {
//         if(y&1)
//         res*=x;

//         y>>=1;
//         x=x*x;
//     }
//     return res;
// }

// void swap(ll &a,ll &b)
// {
//     a ^= b; 
//     b ^= a; 
//     a ^= b;
// }
// int main(int argc, char* argv[])
// {
//     ios::sync_with_stdio(false);
//     cin.tie(NULL);
//     int h,n;
//     cin>>h>>n;
//     VII wt(n),v(n);

//     for(int i=0;i<n;++i)
//     cin>>wt[i]>>v[i];

//     int dp[h+1]; 
//     memset(dp, INT_MAX, sizeof dp); 
//     int ans = 0; 
  
//     // Fill dp[] using above recursive formula 
//     for (int i=0; i<=h; i++) 
//       for (int j=0; j<n; j++) 
//          if (wt[j] <= i) 
//             dp[i] = min(dp[i], dp[i-wt[j]]+v[j]); 
  
//     cout<<dp[h]; 
//     return 0;
// }

/******************************************
* AUTHOR : RAJAGOPALAN *
* NICK : ARNO *
* INSTITUTION : VIT *
******************************************/
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define alli(a, n, k) (a+k),(a+n+k)
#define FP(i, a, b, k) for(__typeof(a) i = a;i < b;i += k)
#define FS(i, a, b, k) for(__typeof(a) i = a;i > b;i -= k)
#define IT(it, a) for(__typeof(a.begin()) it = a.begin();it != a.end(); ++it)

#define eps 1e-6
#define pi 3.141592653589793
using namespace std;

template<class T> inline T gcd(T x, T y) { if (!y) return x; return gcd(y, x%y);}
typedef vector<int> VII;
typedef vector<ll> VLL;
typedef pair<int, int> PII;
typedef vector< pair<int, int> > VPII;
typedef vector< pair<int, PII > > VPPI;
const int MOD = 1e9 + 7;
const int INF = 1e9;
ll fastpower(ll x,ll y)
{
    ll res=1;
    while(y>0)
    {
        if(y&1)
        res*=x;

        y>>=1;
        x=x*x;
    }
    return res;
}

void swap(ll &a,ll &b)
{
    a ^= b; 
    b ^= a; 
    a ^= b;
}

ll dp(ll n)
{
    if(n<0)return 0;
    if(n==1)return 1;

    return 1+2*dp(n/2); 
}
int main(int argc, char* argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin>>n;
    cout<<dp(n);
    return 0;
}

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

//*********************************************************
// 最大公約数（Greatest Common Divisor）を返す。
// 引数に０がある場合は０を返す。
//*********************************************************

int gcd( int m, int n )
{
	// 引数に０がある場合は０を返す
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
	// ユークリッドの方法
	while( m != n )
	{
		if ( m > n ) m = m - n;
		else         n = n - m;
	}
	return m;
}//gcd

//*********************************************************
// 最小公倍数（Least Common Multiple）を返す。
// 引数に０がある場合は０を返す。
//*********************************************************
int lcm( int m, int n )
{
	// 引数に０がある場合は０を返す
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
	return ((m / gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}//lcm

int main(){

	int x,y;
	
	while(std::cin>>x>>y){
		
		std::cout << gcd(x,y) << ' ' << lcm(x,y) << std::endl;
	}
}

Measured memory_bytes: 1156
#include <bits/stdc++.h>
#define LL long long

using namespace std;

int main(){
  LL n;
  LL res=0;
  cin>>n;
  for(LL i=1;i<=n;i++){
  	if(i%3!=0 && i%5!=0)res+=i;
  }
  cout<<res<<endl;
}

Measured memory_bytes: 3636
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
        int[] a = new int[N];
        for(int i = 0; i < N;i++ ){
            a[i] = Integer.parseInt(sc.next());
        }
        int count = 0;
        int max = 0;
        for(int i = 0; i < N-1;i++ ){
            if(a[i+1] <= a[i]){
                count+=1;
            }else{
                count=0;
            }
            if(max < count){
                max = count;
            }
        }
        System.out.println(max);
    }
}

Measured memory_bytes: 48920
#include <bits/stdc++.h>
#define ALL(A) (A).begin(), (A).end()
#define ll long long
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const ll mod = 1e9 + 7;
const ll INF = -1 * ((1LL << 63) + 1);
const int inf = -1 * ((1 << 31) + 1);

int a[1001],b[1001];
int dp[10005]; // dp[i] := hpをi減らす攻撃の最小の魔力

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int h,n;
    cin >> h >> n;
    rep(i,n){
        cin >> a[i] >> b[i];
    }
    rep(i,10005)dp[i] = 1e9+7;
    dp[0] = 0;
    rep(i,10005){
        rep(j,n){
            if(i>=a[j])chmin(dp[i],dp[i-a[j]]+b[j]);
            else chmin(dp[i],b[j]);
        }
    }
    cout << dp[h] << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include <stdio.h>
#include<string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstdint>
#include <queue> 
#include <map>
#include <set>
#define MOD 1000000007
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n)  FOR(i,0,n)
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
typedef long long ll;
using namespace std;

ll lucas[87] = {2,1};

ll Lucas(int n){
  FOR(i,2,n+1){
    lucas[i] = lucas[i-1] + lucas[i-2];
  }
  return lucas[n];
}

int main(){

  int n;
  cin >> n;
  
  cout << Lucas(n) << endl;

 return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
template<typename T>
void fin(T a){
  cout<<a<<endl;
  exit(0);
}
template<typename T>
void chmin(T &a,T b){
  if(a>b)a=b;
}
template<typename T>
void chmax(T &a,T b){
  if(a<b)a=b;
}
using ld=long double;

signed main(){
  ld L;cin>>L;
  cout<<fixed<<setprecision(12)<<(L/3)*(L/3)*(L/3)<<endl;
}


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

int main() {
    bool flag = true;
    string s;
    cin >> s;
    for (int i = 0; i < s.length(); i += 2) {
        if (s[i] == 'L') {
            flag = false;
            break;
        }
    }
    if (flag) {
        for (int i = 1; i < s.length(); i += 2) {
            if (s[i] == 'R') {
                flag = false;
                break;
            }
        }
    }
    if (flag) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

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

#define REP(i,m,n) for(int i=(m); i<(int)(n); i++)
#define RREP(i,m,n) for(int i=(int)(n-1); i>=m; i--)
#define rep(i,n) REP(i,0,n)
#define rrep(i,n) RREP(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define fi first
#define se second
#define debug(...) {cerr<<"[L"<<__LINE__<<"] "; _debug(__VA_ARGS__);}

template<typename T>
string join(const vector<T>&v, string del=", "){ stringstream s;
    for(auto x : v) s << del << x; return s.str().substr(del.size());
}
template<typename T>
ostream& operator<<(ostream& o, const vector<T>&v){
    if(v.size()) o << "[" << join(v) << "]"; return o;
}
template<typename T>
ostream& operator<<(ostream& o, const vector<vector<T> >&vv){
    int l = vv.size();
    if(l){ o<<endl; rep(i,l) o << (i==0 ? "[ " : ",\n  " ) << vv[i] << (i==l-1 ? " ]" : ""); }
    return o;
}
template<typename T1, typename T2>
ostream& operator<<(ostream& o, const map<T1, T2>& mp){
    for(auto p : mp){
        o<< p.fi << ": " << p.se << ", ";
    }
    return o;
}
inline void _debug(){cerr<<endl;}
template<class First, class... Rest>
void _debug(const First& first, const Rest&... rest){cerr<<first<<" ";_debug(rest...);}

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;

const double PI = (1*acos(0.0));
const double EPS = 1e-9;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
const ll mod = 1e9 + 7;

inline void finput(string filename) {
    freopen(filename.c_str(), "r", stdin);
}

pii t[2<<19];
int main(){
    ios_base::sync_with_stdio(0);
    // finput("./input");
    int n; cin >> n;
    rep(i,n){
        int v, w;
        cin >> v >> w;
        t[i] = pii(v, w);
    }

    int L = 100010;
    int K = min(n+1, 1<<10);
    vvl dp(K+1, vl(L));
    REP(i,1,K){
        int v = t[i-1].fi, w = t[i-1].se;
        int par = i >> 1;
        rep(j,L){
            dp[i][j] = dp[par][j];
            if(j-w >= 0) dp[i][j] = max(dp[i][j], dp[par][j-w] + v);
        }
    }

    int q; cin >> q;
    rep(_,q){
        ll u, l; cin >> u >> l;
        ll ans = 0;
        if(u < K){
            ans = dp[u][l];
        }else{
            vi vs;
            while(u >= K){
                vs.push_back(u);
                u >>= 1;
            }
            int d = vs.size();
            rep(i,1<<d){
                ll v = 0, w = 0;
                rep(j,d){
                    if(i >> j & 1){
                        v += t[vs[j]-1].fi;
                        w += t[vs[j]-1].se;
                    }
                }
                if(l-w >= 0) ans = max(ans, dp[u][l-w] + v);
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 809744
#include <stdio.h>

int main(){
   int i,a;
   char s[4],t[4];
 
   scanf("%s",s);
   scanf("%s",t);
   for (a=i=0;i<3;i++) 
      if (s[i]==t[i]) a++;
   printf("%d",a);
   return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define INF 2147483647
#define INF_LL 9223372036854775807
#define MOD 1000000007
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;


int main() {
	int N;
	cin >> N;
	vector<int> h(N);
	for (int i = 0; i < N; i++)cin >> h[i];
	vector<int>dp(N, INF);
	dp[0] = 0;
	for (int i = 0; i < N - 1; i++) {
		dp[i + 1] = min(dp[i] + abs(h[i + 1] - h[i]), dp[i + 1]);
		if(i != N-2)dp[i + 2] = min(dp[i] + abs(h[i + 2] - h[i]), dp[i + 2]);
	}
	cout << dp[N - 1] << endl;
	return 0;
}

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

// TYPEDEFS
typedef long long int li;
typedef unsigned long long int uli;
typedef vector<int> vi;
typedef vector<li> vli;
typedef vector<string> vs;
typedef pair<int, int> ii;
typedef pair<li, li> ll;
typedef pair<int, char> ic;
typedef pair<char, int> ci;
typedef pair<li, char> lc;
typedef pair<char, li> cl;
typedef vector<ic> vic;
typedef vector<ci> vci;
typedef vector<lc> vlc;
typedef vector<cl> vcl;
typedef map<int, int> mii;
typedef map<li, li> mll;
typedef map<char, int> mci;
typedef map<int, char> mic;
typedef map<li, char> mlc;
typedef map<char, li> mcl;
typedef map<char, bool> mcb;
typedef map<int, bool> mib;
typedef map<li, bool> mlb;
typedef set<int> si;
typedef set<li> sl;
typedef set<char> sc;
typedef priority_queue<int> pqi;
typedef priority_queue<li> pql;

// DEFINITIONS
#define fi(i, a, b, jump) \
    for (int i = int(a); i <= int(b); i += jump)
#define fir(i, a, b, jump) \
    for (int i = int(b); i >= int(a); i -= jump)
#define fl(i, a, b, jump) \
    for (li i = li(a); i <= li(b); i += jump)
#define flr(i, a, b, jump) \
    for (li = li(b); i >= li(a); i -= jump)
#define fv(v) \
    for (int i = 0; i < v.size(); ++i)
#define fvr(v) \
    for (int i = v.size()-1; i >= 0; --i)
#define fm(mp) \
    for (it = mp.begin(); it != mp.end(); ++it)
#define mem(arr, val) \
    memset(arr, val, sizeof(arr))

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    li n,k,q, in;
    cin >> n >> k >> q;
    li ans[n+1];
    memset(ans, 0, sizeof(ans));
    li maxi = -1;
    fl(i,1,q,1){
        cin >> in;
        ++ans[in];
        if(ans[in] > maxi) maxi = ans[in];
    }
    if(q < k){
        fl(i, 1 , n , 1){
            cout << "Yes" << endl;
        }
    }
    else{
        fl(i,1, n, 1){
            if(ans[i] -q + k > 0) cout << "Yes";
            else cout << "No";
            cout << endl;
        }
    }
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int inf = 1e9;
const ll INF = 1e18;
const double pi = 3.14159265358979323846;

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

	ll ans=(x/500)*1000+((x%500)/5)*5;

	cout<<ans<<endl;
}

Measured memory_bytes: 256
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    x1, x2, x3, x4, x5 = map(int, readline().split())
    if x1 == 0:
        print('1')
    elif x2 == 0:
        print('2')
    elif x3 == 0:
        print('3')
    elif x4 ==0:
        print('4')
    else:
        print('5')

if __name__ == '__main__':
    main()


Measured memory_bytes: 9120
// SPDX-License-Identifier: Apache-2.0
// Copyright (C) 2020 Bjarni Dagur Thor Karason

#include <bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for (__typeof(a) i=(a); i<(b); i++)
#define MP make_pair
#define PB push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
#define INF 1000000000
#define PI 3.14159265359

int main()
{
    ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    vi people(n);
    for (int i = 0; i < n; i++) {
        cin >> people[i];
    }
    ll ans = 1e17;
    for (int i = 1; i <= 100; i++) {
        ll curAns = 0;
        for (auto u : people) {
            curAns += (u - i) * (u - i);
        }
        ans = min(ans, curAns);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
N = int(input())
XY = [[int(_) for _ in input().split()] for _ in range(N)]
ans = -1
for dx, dy in ((1, 1), (-1, 1), (-1, -1), (1, -1)):
    xy2 = sorted(x * dx + y * dy for x, y in XY)
    ans = max(ans, max(xy2) - min(xy2))
print(ans)


Measured memory_bytes: 58780
q, h, s, d = map(int, input().split())
n = int(input())

l2 = min(d, 2*s, 4*h, 8*q)
if n % 2 == 0:
    print((n // 2) * l2)
else:
    print((n // 2) * l2 + min(s, 2*h, 4*q))

Measured memory_bytes: 38384
from heapq import *

#edge {to cost}
#P {mindirection, modeNum}
#G a list which contain informations of nodes

# building G from input
V=int(input())
G=[]
for _ in range(V):
    temp=list(map(int,input().split()))
    l=[]
    for i in range(1,temp[1]+1):
        l.append(temp[2*i:2*(i+1)])
    G.append(l)

que=[] #having the minimum distance
INF=1e8
d=[INF for i in range(V)] #having the distance
d[0]=0
heappush(que,[0,0])

while len(que)!=0:
    p=heappop(que)
    v=p[1]
    if(d[v]<p[0]):
        continue
    for i in range(len(G[v])):
        e=G[v][i]
        if(d[e[0]]>d[v]+e[1]):
            d[e[0]]=d[v]+e[1]
            heappush(que,[d[e[0]],e[0]])
            
for i in range(V):
    print(i,d[i])


Measured memory_bytes: 6184
// see https://github.com/LumaKernel/vimfiles/tree/master/snippets/cp-cpp/temp.snip
/// --- .lumrc Template {{{ ///
#if 0
#define assert(...)
#endif
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using P = tuple<ll, ll>;
using P3 = tuple<ll, ll, ll>;
using VI = vector<int>;
using VL = vector<ll>;
using VP = vector<P>;
using VS = vector<string>;

#define omajinai ios::sync_with_stdio(false);cin.tie(0)

#define FOR(i,a,b) for(int i=int(a);i<int(b);++i)
#define FORI(i,a,b) for(int i=int(a);i<=int(b);++i)
#define REP(i,n) FOR(i,0,n)
#define REPI(i,n) FORI(i,0,n)
#define RFOR(i,a,b) for(int i=int(b)-1;i>=int(a);--i)
#define RFORI(i,a,b) for(int i=int(b);i>=int(a);--i)
#define RREP(i,n) RFOR(i,0,n)
#define RREPI(i,n) RFORI(i,0,n)

#define ALL(a) (a).begin(),(a).end()
#define UNIQUE(a) (a).erase(unique(ALL(a)),(a).end())
#define PB push_back
#define EACH(i,c) REP(i,(c).size())
#define REACH(i,c) RREP(i,(c).size())
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(ALL(c))

#define BR cout<<"\n";

#ifdef DEBUG
#define dump(...) cerr<<"["<<__LINE__<< "] "<<#__VA_ARGS__<<" = "<<make_tuple(__VA_ARGS__)<<"\n";
#else
#define dump(...)
#endif

#define YES(x) cout<<((x)?"YES":"NO")<<"\n";
#define Yes(x) cout<<((x)?"Yes":"No")<<"\n";
#define yes(x) cout<<((x)?"yes":"no")<<"\n";

inline int omajinai_int_in(){omajinai;int n;cin>>n;return n;}
inline ll omajinai_ll_in(){omajinai;ll n;cin>>n;return n;}
inline string omajinai_string_in(){omajinai;string n;cin>>n;return n;}
inline int int_in(){int n;cin>>n;return n;}
inline ll ll_in(){ll n;cin>>n;return n;}
inline string string_in(){string n;cin>>n;return n;}
#define oini omajinai_int_in()
#define oinl omajinai_ll_in()
#define oins omajinai_string_in()
#define ini int_in()
#define inl ll_in()
#define ins string_in()

#define isInside(y,x) (0<=(y)&&(y)<h&&0<=(x)&&(x)<w)

#define fi(x) (get<0>(x))
#define se(x) (get<1>(x))
#define th(x) (get<2>(x))
#define fo(x) (get<3>(x))
#define fif(x) (get<4>(x))

template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { o << '{'; EACH(i, v) o << v[i] << (i != v.size()-1 ? ", " : ""); o << "}";  return o; }

template<int n, class...T> typename enable_if<(n>=sizeof...(T))>::type _ot(ostream &, tuple<T...> const &){}
template<int n, class...T> typename enable_if<(n< sizeof...(T))>::type _ot(ostream & os, tuple<T...> const & t){ os << (n==0?"":", ") << get<n>(t); _ot<n+1>(os, t); }
template<class...T> ostream & operator<<(ostream & os, tuple<T...> const & t){ _ot<0>(os, t); return os; }

template <typename T> inline void smax(T &a, T b) { a = a > b ? a : b; }
template <typename T> inline void smin(T &a, T b) { a = a < b ? a : b; }

constexpr double PI = acos(-1);

/// }}}--- ///

constexpr int INF = 1e9+1;
constexpr ll LINF = 1e18+1;
constexpr int MOD = 1e9+7;

int solve() {
int f[3][3];
REP(i,3)REP(j,3)cin>>f[i][j];
REP(i,3){
int m=INF;
REP(j,3)smin(m, f[i][j]);
REP(j,3)f[i][j] -= m;
}

REP(j,3){
int b=1;
REP(i,3)b&=f[i][j] == f[0][j];
if(!b) return 0;
}
return 1;
}
int main() {Yes(solve());}

//


Measured memory_bytes: 256
#include <array>
#include <cstdio>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i, m, n) for (int i = (m); (i) < int(n); ++(i))
using ll = long long;
using namespace std;

constexpr int mod = 1e9+7;
int main() {
    // input
    int n; ll a, b; scanf("%d%lld%lld", &n, &a, &b);
    vector<ll> s(n); repeat (i, n) scanf("%lld", &s[i]);
    if (a > b) swap(a, b);
    // solve
    s.insert(s.begin(), s.front() - a - b);
    s.insert(s.end(),   s.back()  + a + b);
    s.insert(s.end(),   s.back()  + a + b);
    vector<array<int, 2> > dp(n + 2);
    vector<int> acc(dp.size() + 1);
    dp[0][0] = 1;
    acc[1] = 1;
    int l_l = 0, l_r = 0;
    repeat_from (r, 1, dp.size()) {
        while (l_r < r - 1 and s[l_r] + b <= s[r]) ++ l_r;
        if (l_l <= l_r) {
            dp[r][0] = (acc[l_r] - acc[l_l] +(ll) mod) % mod;
        }
        if (not (s[r - 1] + a <= s[r])) l_l = r - 1;
        dp[r][1] = (s[r - 1] + b <= s[r]) ? (dp[r - 1][0] + dp[r - 1][1]) % mod : 0;
        acc[r + 1] = (0ll + acc[r]
                + (s[r - 1] + a <= s[r + 1] ? dp[r][0] : 0)
                + dp[r][1] ) % mod;
    }
    // output
    int result = (dp[n + 1][0] + dp[n + 1][1]) % mod;
    printf("%d\n", result);
    return 0;
}



Measured memory_bytes: 2164
#include <stdio.h>

int main(void) {
	char a, b, c;
	scanf("%c %c %c", &a, &b, &c);
	if((a==b && a!=c) || (a==c && a!=b) || (b==c && a!=b))
		printf("Yes");
	else
		printf("No");
	
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) for (long long i = 0, max_i = (n); i < max_i; i++)
#define REPI(i, a, b) for (long long i = (a), max_i = (b); i < max_i; i++)
#define ALL(obj) begin(obj), end(obj)
#define RALL(obj) rbegin(obj), rend(obj)
#define fi first
#define se second
using ii = pair<int, int>;
vector<ii> dirs = {
  {1, 0}, {0, 1}, {-1, 0}, {0, -1},  // 4方向
  {1, 1}, {-1, 1}, {-1, -1}, {1, -1},  // 斜め
  {0, 0},  // 自身
};
template <class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }
template <class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template <class T, class S> vector<T> make_vec(size_t n, S x) { return vector<T>(n, x); }
template <class T, class... Ts> auto make_vec(size_t n, Ts... ts) { return vector<decltype(make_vec<T>(ts...))>(n, make_vec<T>(ts...)); }

// debug
template <class T> ostream& operator<<(ostream& s, vector<T>& d) { REP (i, d.size()) s << d[i] << (i == d.size() - 1 ? "" : " "); return s; }
template <class T> ostream& operator<<(ostream& s, vector<vector<T>>& d) { REP (i, d.size()) s << d[i] << (i == d.size() - 1 ? "" : "\n"); return s; }
template <class T, class S> ostream& operator<<(ostream& s, pair<T, S>& p) { s << "{" << p.first << ", " << p.second << "}"; return s; }
template <class T, class S> ostream& operator<<(ostream& s, map<T, S> m) { for (auto it = m.begin(); it != m.end(); it++) { s << *it << (next(it) == m.end() ? "" : "\n"); } return s; }
#ifdef _MY_DEBUG
  #define dump(...) cerr << "/* " << #__VA_ARGS__ << " :[" << __LINE__ << ":" << __FUNCTION__ << "]" << endl, dump_func(__VA_ARGS__), cerr << "*/\n\n";
#else
  #define dump(...)
  #define endl "\n"
#endif
void dump_func() { cerr << endl; }
template <class Head, class... Tail> void dump_func(Head&& h, Tail&&... t) { cerr << h << (sizeof...(Tail) == 0 ? "" : ", "), dump_func(forward<Tail>(t)...); }

struct Fast { Fast() { cin.tie(0); ios::sync_with_stdio(false); } } fast;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
constexpr int MOD = 1000000007;
// *************** TEMPLATE END *************** 

signed main() {
  int n; cin >> n;
  vector<vector<ii>> g(n);
  REP (i, n - 1) {
    int u, v, w; cin >> u >> v >> w;
    u--;
    v--;
    g[u].push_back({v, w});
    g[v].push_back({u, w});
  }

  vector<int> ans(123456 + 1);
  function<void(int, int)> dfs = [&](int v, int p) {
    for (ii s: g[v]) if (s.fi != p) {
      dump(s);
      dump(p, ans[p]);
      if (s.se % 2) {
        ans[s.fi] = 1 ^ ans[v];
      } else {
        ans[s.fi] = ans[v];
      }
      dfs(s.fi, v);
    }
  };
  dfs(0, 123456);
  REP (i, n) cout << ans[i] << endl;
}


Measured memory_bytes: 11904
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//BEGIN CUT HERE
const double EPS=1E-8;
typedef vector<double> vec;
typedef vector<vec> mat;
vec gauss_jordan(const mat& A,const vec& b){
  int n=A.size();
  mat B(n,vec(n+1));
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      B[i][j]=A[i][j];
  for(int i=0;i<n;i++) B[i][n]=b[i];
  for(int i=0;i<n;i++){
    int pivot=i;
    for(int j=i;j<n;j++)
      if(abs(B[j][i])>abs(B[pivot][i])) pivot=j;
    swap(B[i],B[pivot]);
    if(abs(B[i][i])<EPS) return vec();
    for(int j=i+1;j<=n;j++) B[i][j]/=B[i][i];
    for(int j=0;j<n;j++){
      if(i!=j){
	for(int k=i+1;k<=n;k++) B[j][k]-=B[j][i]*B[i][k];
      }
    }
  }
  vec x(n);
  for(int i=0;i<n;i++) x[i]=B[i][n];
  return x;
}
//END CUT HERE

signed main(){
  int d;
  while(cin>>d,d){
    vec v(d+3);
    for(int i=0;i<d+3;i++) cin>>v[i];
    int ans=0;
    mat m(d+3,vec(d+2));
    for(int i=0;i<d+3;i++)
      for(int j=0;j<d+1;j++)
	m[i][j]=pow(1.0*i,j);
    for(int i=0;i<d+3;i++){
      for(int j=i+1;j<d+3;j++){
	vec b(d+1);
	mat A(d+1,vec(d+1));
	for(int k=0,l=0;k<d+3;k++)
	  if(i!=k&&j!=k) A[l]=m[k],b[l]=v[k],l++;
	vec x=gauss_jordan(A,b);
	double res[2]={};
	for(int k=0;k<d+1;k++){
	  res[0]+=x[k]*m[i][k];
	  res[1]+=x[k]*m[j][k];
	}
	if(abs(res[0]-v[i])+1e-5>1.0&&abs(res[1]-v[j])<1e-5) ans=i;
	if(abs(res[0]-v[i])<1e-5&&abs(res[1]-v[j])+1e-5>1.0) ans=j;
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}

/*
  verified on 2017/12/31
  
*/

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

using namespace std;

int n = 1, L;
struct edge { int u, v, w; };
vector<edge> res;

int main() {
    cin >> L;
    int tmp = 1;
    while (tmp * 2 <= L) {
        res.push_back({n, n + 1, 0});
        res.push_back({n, n + 1, tmp});
        tmp *= 2; n++;
    }
    while (tmp < L) {
        int id = 1, tmp2 = 1;
        while (tmp2 * 2 < L - tmp)
            id++, tmp2 *= 2;
        res.push_back({id, n, tmp});
        tmp += tmp2;
    }
    cout << n << " " << res.size() << endl;
    for (edge get: res)
        cout << get.u << " " << get.v << " " << get.w << endl;
}


Measured memory_bytes: 256
#define LOCAL
#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second	
#define db 0
#define EPS (1e-7)    //0.0000001 the value
#define PI (acos((ld)-1.0))
#define MAXN (300006)
#define ll long long int 
#define ld long double
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
#define FOR(ii, ss, ee) for(ll ii = ss; ii < (ll)ee; ++ii)
#define space " "
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define ph push
#define btinpct(x) __builtin_popcountll((x))
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
typedef pair <ll, ll> pi;
typedef pair <ll, pi> spi;
typedef pair <pi, pi> dpi;
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss
string to_string(char c) {string s(1,c);return s;}string to_string(bool b){return (b ? "true" : "false");}template <typename A, typename B>string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}template <typename A>string to_string(A v) {bool first = true;string res = "{";for (const auto &x : v) {if (!first) {res += ", ";}first = false;res += to_string(x);}res += "}";return res;}void degug_out() { cerr << endl; }template <typename Head, typename... Tail>void degug_out(Head H, Tail... T) {cerr << " " << to_string(H);degug_out(T...);}inline ll gcd(ll a,ll b){if(a>b)swap(a,b);if(a==0)return b;return gcd(b%a,a);}
#ifdef LOCAL
#define degug(...) cerr << "[" << #__VA_ARGS__ << "]:", degug_out(__VA_ARGS__)
#else
#define degug(...) 42
#define cerr if(0)cout
#endif
ll n;
ll A[MAXN],bit[MAXN]; vector<ll>B;
int main()
{
	FAST
	cin>>n;
	FOR(i,0,n)cin>>A[i];
	FOR(i,0,n){ ll a; cin>>a; B.pb(a); }
	vector<ll>tmp;tmp=B;
	ll sum=0; for(ll b=28;b>=0;--b){
		ll T=(1<<b); ll MOD=2ll*T; for(auto &i:B)i%=MOD; sort(all(B));
		FOR(i,0,n){ ll x=A[i]%MOD;
			bit[b]+=lbd(B,MOD-x)-lbd(B,T-x); //cerr<<MOD-x<<' '<<T-x<<' '<<ubd(B,MOD-x)-lbd(B,T-x)<<'\n';
			bit[b]+=B.end()-lbd(B,MOD-x+T); //cerr<<MOD-x+T<<' '<<B.end()-lbd(B,MOD-x+T)<<'\n';
		}if(b==0)cerr<<bit[b]<<'\n';
		if(bit[b]&1)sum+=(1ll<<b);
		// B=tmp;
	}
	cout<<sum<<'\n';
}


Measured memory_bytes: 5616
#include<iostream>
using namespace std;
int main() {
	int n;
	cin >> n;
	long long int sum = 0;
	for (int i = 1; i <= n; i++) {
		if (i % 3 != 0 && i % 5 != 0) {
			sum += i;
		}
	}
	cout << sum;
	return 0;
}

Measured memory_bytes: 3584
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <numeric> // accumulate(v.begin(), v.end(), 0)

using namespace std;
#define ll long long

/*
  約数
*/
vector<ll> divisor;
void find_divisor(ll N) {
  for(int i=1; i<ceil(sqrt(N))+1; i++) {
    if(N % i == 0)
      divisor.push_back(i);
  }
  int n = divisor.size();
  for(int i=n-1; i>=0; i--) {
    if(N != (ll)pow(divisor[i], 2))
      divisor.push_back(N / divisor[i]);
  }
}

int main(){
  int N;  ll M;
  cin >> N >> M;
  find_divisor(M);
  for(int i=divisor.size()-1; i>=0; i--) {
    if(divisor[i] * N <= M) {
      cout << divisor[i] << endl;
      break;
    }
  }
  return 0;
}


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

int main(){
    double ans=0;
    int n,m;
    
    cin >>n;
    
    for (int i = 0; i < n; i++){
        double a;
        cin >> a;

        ans += 1/a;
    }
    


    cout <<fixed<<setprecision(16)<< (double)(1/ans)  << endl;
    //cout << bunsi/bunbo << endl;

    //if(flag==1)cout << "Yes" <<endl;
    //else cout << "No" <<endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
ll ans = 0;
template< typename T >
struct BinaryIndexedTree {
  vector< T > data;

  BinaryIndexedTree(ll sz) {
    data.assign(++sz, 0);
  }

  T sum(ll k) {
    T ret = 0;
    for(++k; k > 0; k -= k & -k) ret += data[k];
    return (ret);
  }

  void add(ll k, T x) {
    for(++k; k < data.size(); k += k & -k) data[k] += x;
  }
};
int main()
{
ll n , k ;
cin >> n >> k ;
vector<ll> a(n);
rep(i, n){
  cin >> a[i];
  a[i]-=k;
}
vector<ll> s;
s.push_back(0);
rep(i,n){
  s.push_back(a[i]+s[i]);
}
vector<ll> comp=s;//全部突っ込む
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());//隣接要素を削除した後の末尾イテレータからvの末尾まで削除
vector<ll> ss;
rep(i,s.size()){
  ll compnum=lower_bound(comp.begin(), comp.end(), s[i]) - comp.begin();//圧縮後の値
  ss.push_back(compnum);
}
BinaryIndexedTree< ll > bit(n+1);
rep(i,ss.size()){
  ans+=bit.sum(ss[i]);
  bit.add(ss[i],1);
}
cout << ans << endl;
return 0;
}


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

#define YYDBG

int inputs[18];
int N;
int main(void) {
    int A, B;
    int i,j,k;
    int clist[18];
    int tmp_result;
    int result = -1;

    scanf("%d %d\n", &A, &B);
    if ((A+B)%2 == 0) {
        printf("%d\n", (A+B)/2);
    } else {
        printf("IMPOSSIBLE\n");
    }

    return 0;
}



Measured memory_bytes: 128
if __name__ == '__main__':

	A = []
	while True:
		try:
			n = int(input())
			if n == 0:
				break
			else:
				for _ in range(n):
					m = int(input())
					A.append(m)

				A = sorted(A)

				b = 0
				B = []
				for x in range(len(A)-1):
					b += A[x]
					B.append(b)

				print(sum(B))
				A = []

		except EOFError:
			break




Measured memory_bytes: 6196
def main():
    N = int(input())
    l = [[int(s) for s in input().split()] for n in range(N)]
    can = True
    now = [0, 0, 0]
    for i in range(N):
        pos = l[i]
        d = abs(pos[1] - now[1]) + abs(pos[2] - now[2])
        t = pos[0] - now[0]
        if d % 2 != t % 2 or d > t:
            can = False
        now = pos
    if can:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()


Measured memory_bytes: 21156
#include <cstdio>

int main()
{
  int n;
  char s[101];
  scanf("%d%s", &n, s);
  if (n & 1)
  {
    puts("No");
    return 0;
  }
  for (int i = 0; i < n / 2; ++i)
  {
    if (s[i] != s[i + n / 2])
    {
      puts("No");
      return 0;
    }
  }
  puts("Yes");
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#include<queue>
using namespace std;
 
#define what_is(x) cout << #x << " is " << x << endl; 
#define PI acos(-1)
#define hell 1000000007
#define HELL 998244353
#define io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define fix(n) cout << fixed << setprecision(n)
#define mset(a,n) memset(a,n,sizeof a)
#define rep(i,a,b) for (__typeof((b)) i=(a);i<(b);i++)
#define repp(i,a,b,p) for(__typeof((b)) i=(a);i<(b);i+=p)
#define ren(i,a,b) for(__typeof((a)) i=(a);i>=(b);i--)
#define renn(i,a,b,p) for(__typeof((a) i=(a);i>=(b);i-=p)
#define ADD(a,b,c) ((a)%c+(b)%c)%c
#define SUB(a,b,c) ((a)%c-(b)%c+c)%c
#define MUL(a,b,c) (((a)%c)*((b)%c))%c
#define lbd lower_bound
#define ubd upper_bound
#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define all(v) (v).begin(), (v).end()
#define sz(x) (ll)x.size()
// #define out(n) cout<<n<<" "
#define outl(n) cout<<n<<endl
#define bug(n) {outl(n);return;}
#define pii pair<int,int>
#define lim 9223372036854775805
#define ninf -9223372036854775802
#define M 1000000007
#define eps 1e-9
#define MAX 5
#define N 500001
#define db(a) for(auto it:a) {cout<<it<<" ";}cout<<endl;
ll prime[MAX]; 
ll fact[MAX];

const long long INF64 = 1e18;
ll vpow(ll a,ll b,ll p){
    if(b==0)
        return 1;
    if(b==1)
            return a;
    ll temp=vpow(a,b/2,p);
    temp*=temp;
    temp%=p;
    if(b%2==0)
        return temp;
    temp=temp*a;
    temp%=p;
    return temp;
}

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

 
ll inverseMod(ll a,ll b,ll p){
    if(b==0)
        return 1;
    ll temp=vpow(b,p-2,p);
    ll ans=temp*a;
    ans%=p;
    return ans;
}
void sieve() 
{ 
    prime[0] = prime[1] = 1; 
    for (ll i = 2; i < MAX; i++) { 
        if (prime[i] == 0) {
            for (int j = i * 2; j < MAX; j += i) { 
                if (prime[j] == 0) { 
                    prime[j] = i; 
                } 
            } 
            prime[i] = i; 
        } 
    } 
}

void factorial(){
    fact[0]=1;
    fact[1]=1;
    rep(i,2,MAX){
        fact[i]=(fact[i-1]*i);
        // fact[i]%=M;
    }
}

void solve(ll ttt){
	string s;
    cin>>s;
    ll sum=0;
    rep(i,0,sz(s)){
        sum+=(s[i]-'0');
        sum%=9;
    }
    if(sum==0)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
}

int main(){
    io;
   
    // sieve();
    // factorial();
#ifndef ONLINE_JUDGE
    freopen("input1.txt","r",stdin);
   // freopen("output1.txt","w",stdout);
#endif
    ll t=1;
    //cin>>t;
    fix(12);
    rep(q,1,t+1){
        // cout<<"Case #"<<q<<": ";
         solve(q);
        //solve2();
    }
    return 0;
    
}


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

typedef long long i64;
const int N = 1e5 + 10;
i64 n, m;
char s[N], t[N];
map<i64, char> hav;

i64 gcd(i64 a, i64 b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    cin >> n >> m;
    scanf("%s", s + 1);
    scanf("%s", t + 1);
    i64 lcm = m * n / gcd(n, m);
    for (i64 i = 1; i <= n; ++i) hav[(i - 1) * lcm / n+1]=s[i];
    for (i64 i = 1; i <= m; ++i) if (hav[(i-1)*lcm/m+1] && hav[(i-1)*lcm/m+1]!= t[i]) { puts("-1"); return 0;}
    cout << lcm << endl;
    return 0;
}


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

using namespace std;

constexpr int INF = 0x3f3f3f3f;
constexpr int H = 20;
constexpr int W = 20;
constexpr int N = H * W;

int dir[2][4] = {{-1, 1, 0, 0}, {0, 0, -1, 1}};
vector<int> g[N + 1];
int dist[N + 1][N + 1];
char mat[H + 2][W + 2];
int h, w, n; // (Input)

/* O(V^3) - Returns true if there's a negative cycle in the graph. */
bool floyd_warshall() {
	// Initializing.
	memset(dist, 0x3f, sizeof(dist));

	// Filling distance matrix with the edges.
	for (int u = 1; u <= n; u++) {
		dist[u][u] = 0;

		for (int i = 0; i < g[u].size(); i++) {
			int v = g[u][i];
			dist[u][v] = 1;
		}
	}

	// For every intermediate vertex k.
	for (int k = 1; k <= n; k++) {
		// For every starting vertex i.
		for (int i = 1; i <= n; i++) {
			// For every ending vertex j.
			for (int j = 1; j <= n; j++) {
				// If there is a better path using k as intermediate vertex.
				if (dist[i][k] + dist[k][j] < dist[i][j]) {
					dist[i][j] = dist[i][k] + dist[k][j];
				}
			}
		}
	}

	// Checking for negative cycles.
	for (int u = 1; u <= n; u++) {
		if (dist[u][u] < 0) {
			return true; // u belongs to a negative cycle.
		}
	}

	// No negative cycles.
	return false;
}

bool inside(int x, int y) {
	return 0 <= x and x < h and 0 <= y and y < w;
}

bool valid(int x, int y) {
	return inside(x, y) and mat[x][y] != '#';
}

int main() {
	int ans, i, j, k, u, v;

	scanf("%d%d", &h, &w);
	n = h * w;

	for (i = 0; i < h; i++) {
		scanf(" %s", mat[i]);
	}

	for (i = 0; i < h; i++) {
		for (j = 0; j < w; j++) {
			if (valid(i, j)) {
				u = i * w + j + 1;

				for (k = 0; k < 4; k++) {
					int xf = i + dir[0][k];
					int yf = j + dir[1][k];
					v = xf * w + yf + 1;

					if (valid(xf, yf)) {
						g[u].push_back(v);
						g[v].push_back(u);
					}
				}
			}
		}
	}

	floyd_warshall();
	ans = 0;

	for (u = 1; u <= n; u++) {
		for (v = 1; v <= n; v++) {
			if (dist[u][v] < INF) {
				ans = max(ans, dist[u][v]);
			}
		}
	}

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

	return 0;
}

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

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using Pi = pair<int, int>;
using Tapris = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

struct UF {
  vint data;
  UF(){}
  void init(int n) {
    resz(data, n, -1);
  }
  int size(int x) {
    return -data[find(x)];
  }
  int find(int x) {
    return data[x] < 0 ? x : data[x] = find(data[x]);
  }
  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return false;
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return true;
  }
};

int N, M, K;
vint c, a, b, w;
UF uf;

struct edge {
  int u, v, w;
  edge(){}
  edge(int u, int v, int w):u(u), v(v), w(w){}
  bool operator < (const edge& e) const {
    return w < e.w;
  }
};

vector<edge> es;

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  cin >> N >> M >> K;
  vint par(K+1, -1);
  int cnt = 0;
  resz(c, N);
  rep(i, N) cin >> c[i];
  resz(a, M);
  resz(b, M);
  resz(w, M);
  rep(i, M) {
    cin >> a[i] >> b[i] >> w[i];
    --a[i], --b[i];
    es.emplace_back(a[i], b[i], w[i]);
  }
  sort(all(es));
  /*
  uf.init(K+1);
  int sum = 0;
  for(edge e : es) {
    if(uf.unite(c[e.u], c[e.v])) sum += e.w;
  }
  if(uf.size(1) == K) cout << sum << endl;
  else cout << -1 << endl;
  */
  uf.init(N);
  rep(i, N) {
    if(c[i] == 0) continue;
    if(par[c[i]] == -1) {
      par[c[i]] = i;
      ++cnt;
    } else {
      uf.unite(par[c[i]], i);
    }
  }
  int num = 0;
  int sum = 0;
  for(edge e : es) {
    if(uf.unite(e.u, e.v)) {
      ++num;
      sum += e.w;
    }
    if(num == K-1) break;
  }
  if(num == K-1) cout << sum << endl;
  else cout << -1 << endl;

  return 0;
}


Measured memory_bytes: 8820
n,a,b,c,d=map(int,input().split())
way=list(input())

def not_double_stone(way):
    already=False
    for i in way:
        if i=="#" and already:
            return False
        elif i=="#":
            already=True
        else:
            already=False
    return True

def can_over(way):
    count=0
    for i in way:
        if i==".":
            count+=1
        else:
            count=0
        if count==3:
            return True
    return False

if c<d:
    if not_double_stone(way[b-1:d]) and not_double_stone(way[a-1:c]):
        answer='Yes'
    else:
        answer='No'
else:
    if can_over(way[b-2:d]):
        if not_double_stone(way[a-1:c]):
            answer='Yes'
        else:
            answer='No'
    else:
        if not_double_stone(way[a-1:c]) and way[d-2]!="#" and way[d]!="#":
            answer='Yes'
        else:
            answer='No'

print(answer)

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

using namespace std;
using ll=long long;
using ld=long double;
using P=pair<ll,ll>;
#define FOR(i,n,m) for(ll i=n; i<(ll)m;i++)
#define FORr(i,n,m) for(ll i=n; i>(ll)m; i--)
#define FORm(i,m) for(auto i=m.begin();i!=m.end();i++)
#define VEC2(x,a,b) vector<vector<ll>> x = vector<vector<ll>>(a,vector<ll>(b,0))
#define sortAl(v) sort(v.begin(),v.end())
#define sortAlr(v) sort(v.begin(),v.end()); reverse(v.begin(),v.end())
#define cinv(v,n,m) FOR(i,n,m) cin>>v.at(i)
#define coutv(v,n,m) FOR(i,n,m) cout<<v.at(i) <<" "; cout<<endl
#define cout(n) cout<<fixed<<setprecision(n)
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  string x,y;
  cin>>x>>y;
  vector<pair<char,ll>> vx(x.size());
  vector<pair<char,ll>> vy(y.size());

  FOR(i,0,x.size()){
    vx[i]=make_pair(x[i],i);
    vy[i]=make_pair(y[i],i);
  }

  vector<pair<char,ll>> vxs(x.size());
  vector<pair<char,ll>> vys(y.size());
  vxs=vx;
  vys=vy;
  sortAl(vxs);
  sortAl(vys);
  string res="Yes";
  FOR(i,1,x.size()){
    ll x1=vxs[i].second;
    ll x2=vxs[i-1].second;
    ll y1=vys[i].second;
    ll y2=vys[i-1].second;

    if(vxs[i].first==vxs[i-1].first&&
       vy[x1].first!=vy[x2].first)res="No";
    if(vys[i].first==vys[i-1].first&&
       vx[y1].first!=vx[y2].first)res="No";

  }
  cout<<res<<endl;


}


Measured memory_bytes: 13460
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }
 
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
  ll n,x;cin>>n>>x;
  vector<ll> m(n); for(auto&in:m)cin>>in;
  ll sum=accumulate(m.begin(),m.end(),0LL);
  cout<<n+(x-sum)/(*min_element(m.begin(),m.end()))<<endl;
    return 0;
}

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

const double EPS = 1e-10;
const ll INF = 100000000;
const ll MOD = 1000000007;

int n;
int si[5000], par[5000];
vector<int> e[5000];
vector<int> vec;
ll ans = 0;
ll dp[5001][5001];

vector<ll> pre[5001];
ll kai[5001];

ll mod_pow(ll x, ll y) {
    ll ret = 1;
    while (y) {
        if (y&1) ret = ret * x % MOD;
        x = x * x % MOD;
        y /= 2;
    }
    return ret;
}

void pre_calc() {
    kai[0] = 1;
    for (ll i = 1; i <= 5000; i++) {
        kai[i] = kai[i-1] * i % MOD;
    }
    rep(i,vec.size()) {
        pre[i].resize(vec[i]+1);
        pre[i][0] = 1;
        for (int j = 1; j <= vec[i]; j++) {
            pre[i][j] = kai[vec[i]] * mod_pow(kai[j], MOD-2) % MOD;
            pre[i][j] = pre[i][j] * mod_pow(kai[vec[i]-j], MOD-2) % MOD;
            pre[i][j] = pre[i][j] * pre[i][j] % MOD;
            pre[i][j] = pre[i][j] * kai[j] % MOD;
        }
    }
}

void dfs(int v) {
    rep(i,e[v].size()) {
        if (e[v][i] == par[v]) continue;
        par[e[v][i]] = v;
        dfs(e[v][i]);
    }
    si[v] = 1;
    rep(i,e[v].size()) {
        si[v] += si[e[v][i]];
    }
}

int main(){
    cin >> n;
    rep(i,n-1) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(0);
    int center = -1;
    rep(i,n) {
        bool ok = true;
        rep(j,e[i].size()) {
            if (e[i][j] == par[i]) {
                if (n-si[i] >= (n+1)/2) {
                    ok = false;
                    break;
                }
            } else {
                if (si[e[i][j]] >= (n+1)/2) {
                    ok = false;
                    break;
                }
            }
        }
        if (ok) {
            center = i;
            break;
        }
    }
    if (center == -1) {
        ans = 1;
        for (ll i = 1; i <= n/2; i++) {
            ans = ans * i % MOD;
        }
        ans = ans * ans % MOD;
        cout << ans << endl;
        return 0;
    }
    rep(i,e[center].size()) {
        if (e[center][i] == par[center]) {
            vec.push_back(n-si[center]);
        } else {
            vec.push_back(si[e[center][i]]);
        }
    }
    pre_calc();
    
    /*
    rep(i,vec.size()) {
        rep(j,pre[i].size()) {
            cout << pre[i][j] << " ";
        }
        cout << endl;
    }
    */
    
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    rep(i,vec.size()) {
        rep(j,n) {
            rep(k,vec[i]+1) {
                if (j-k < 0) break;
                dp[i+1][j] += (dp[i][j-k]*pre[i][k])%MOD;
            }
            dp[i+1][j] %= MOD;
        }
    }
    /*
    rep(i,n+1) {
        rep(j,n+1) {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
    */
    ans = 0;
    rep(i,n) {
        ll adder = (i%2==0?1LL:-1LL) * kai[n-i] * dp[vec.size()][i]%MOD;
        ans = (ans+adder)%MOD;
    }
    cout << (ans+MOD)%MOD << endl;
}
































Measured memory_bytes: 196352
#include <bits/stdc++.h>
#define pb push_back
#define all(a) a.begin(),a.end()
#define forn(i,n) for(int i=0;i<int(n);i++)
#define forr(i,n) for(int i=int(n-1);i>=0;i--)
#define fora(i,a,b) for(int i=int(a);i<=int(b);i++)
#define forb(i,a,b) for(int i=int(a);i>=int(b);i--)
#define mod 1000000007
using namespace std;
using ll=long long int;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<ll> vii;
typedef pair<ll ,ll> pii;
template<typename T>
string ts(T v)
{
	string res="{";
	bool r=true;
	for(const auto &x:v)
	{
		if(!r)res+=",";
		r=false;
		res+=to_string(x);
	}
	res+="}";
	return res;
}
ll search(ll* arr,ll n,ll key)
{
	ll s=0,e=n-1,ans=-1;
	while(s<=e)
	{
		ll mid=(s+e)/2;
		if(arr[mid]<=key)
		{
			ans=mid;
			s=mid+1;
		}
		else
		{
			e=mid-1;
		}
	}

	return ans;
}
void solve()
{
	ll n,m,k;
	cin>>n>>m>>k;
	ll a[n],b[m];
	forn(i,n)cin>>a[i];
	forn(i,m)cin>>b[i];
	ll pre[n];
	pre[0]=a[0];
	fora(i,1,n-1)pre[i]=pre[i-1]+a[i];

	ll pre2[m];
	pre2[0]=b[0];
	fora(i,1,m-1)pre2[i]=pre2[i-1]+b[i]; 
	ll ans=0;
	forn(i,n)
	{
		ll x=k-pre[i];
		if(x<0)break;
		ll p=search(pre2,m,x);
		if(p>=0)
		{
			ans=max(ans,i+p+2);
		}
		else
		{
			ans=max(ans,(ll)i+1);
		}
	}
	forn(i,m)
	{
		ll x=k-pre2[i];
		if(x<0)break;
		ll p=search(pre,n,x);
		if(p>=0)
		{
			ans=max(ans,i+p+2);
		}
		else
		{
			ans=max(ans,(ll)i+1);
		}
	}
	cout<<ans<<endl;
}
int main()
{
	#ifndef ONLINE_JUDGE
    freopen("ip.txt", "r", stdin);
    freopen("op.txt", "w", stdout);
    #endif
    ios::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0);
    int t=1;
   // cin>>t;
    while(t--)
   	solve();
}


Measured memory_bytes: 9896
from sys import stdin

N, K = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]

A.sort()
c = 1
ans = 0
inf = 10 ** 9 + 7
fact_list = [1] * (N + 1)
fact_inv = [1] * (N + 1)
f = 1

for i in range(1, N + 1):
    f *= i
    f %= inf
    fact_list[i] = f

for i in range(1, N + 1):
    fact_inv[i] = pow(fact_list[i], inf - 2, inf)

for i in range(N - K + 1):
    tmp_min = A[i]
    tmp_max = A[N - i - 1]
    d = (tmp_max - tmp_min) % inf
    n = fact_list[N - i - 1] * fact_inv[K - 1] * fact_inv[N - i -K] % inf
    ans += d * n
    ans %= inf

print(int(ans))

Measured memory_bytes: 63344
#include <bits/stdc++.h>
using namespace std;
int n,x[10005],y[100005];
double s[10005],soo;
double av;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&x[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&y[i]);
    for(int p=1;p<=3;p++)
    {
        double t=0;
        for(int i=1;i<=n;i++)
            t+=pow((double)abs(x[i]-y[i]),(double)p);
        s[p]=pow(t,(double)1/p);
    }
    for(int i=1;i<=n;i++)
        soo=max(soo,(double)abs(x[i]-y[i]));
    for(int i=1;i<=3;i++) printf("%f\n",s[i]);
    printf("%f\n",soo);
}



Measured memory_bytes: 3416