akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"

#if debug
#include "printer.hpp"
#define dump(a) cerr << #a << "(" << __LINE__ << ") = " << a << endl;
#else
#define dump(...)
#endif

#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define repr(i, a, b) for (int i = (b)-1; i >= a; i--)
#define all(x) (x).begin(), (x).end()

using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
const ll mod = 1000000007;

ll pow(ll x, ll y) {
  ll ret = 1, tmp = x;
  while (y) {
    if (y % 2) ret = ret * tmp % mod;
    tmp = tmp * tmp % mod;
    y /= 2;
  }
  return ret;
}

ll inverse(ll x) { return pow(x, mod - 2); }

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(8);

  ll N, u, v;
  cin >> N >> u >> v;
  u--;
  v--;

  vvi G(N);
  rep(i, 0, N - 1) {
    ll a, b;
    cin >> a >> b;
    a--;
    b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }

  vi dist_t(N, -1), dist_a(N, -1);
  dist_t[u] = 0;
  dist_a[v] = 0;

  {
    queue<ll> q;
    q.push(u);
    while (q.size()) {
      ll fr = q.front();
      q.pop();
      for (ll to : G[fr]) {
        if (dist_t[to] == -1) {
          dist_t[to] = dist_t[fr] + 1;
          q.push(to);
        }
      }
    }
  }
  {
    queue<ll> q;
    q.push(v);
    while (q.size()) {
      ll fr = q.front();
      q.pop();
      for (ll to : G[fr]) {
        if (dist_a[to] == -1) {
          dist_a[to] = dist_a[fr] + 1;
          q.push(to);
        }
      }
    }
  }

  dump(dist_t);
  dump(dist_a);

  ll x = -1, y = -1;
  rep(i, 0, N) {
    if (dist_t[i] < dist_a[i]) {
      if (y < dist_a[i]) {
        x = dist_t[i];
        y = dist_a[i];
      }
    }
  }

  dump(x);
  dump(y);
  ll ans = x;
  y -= x;

  bool f = true;
  while (1) {
    if (f) 
      y--;
    else
      y++;
    f = !f;
    if (y == 0) {
      cout << ans << endl;
      return 0;
    }
    y--;
    ans++;
    if (y == 0) {
      cout << ans << endl;
      return 0;
    }
  }
}


Measured memory_bytes: 8064
#include <bits/stdc++.h>
using namespace std;
const long long N = 1e6;
int d()
{
    int ret;
    scanf("%d", &ret);
    return ret;
}
long long lld()
{
    long long ret;
    scanf("%lld", &ret);
    return ret;
}
bool cmp(pair<int, int> s, pair<int, int> f)
{
    if (f.first > s.first)
        return true;
    else if (f.first == f.second && f.second < s.second)
        return true;
    else
        return false;
}
long long fact(long long n)
{
    if(n==1)
        return 1;
    return n * fact(n-1);
}
pair<int ,char>p;
pair<int ,char>p1;
pair<int ,char>p2;
int main(){
    int n=d();
    printf("%d\n",(n*800)-((n/15)*200));



}


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


int main(){
	int t,n;
	for(int i = 0; i < 4; i++){
		cin >> t >> n;
		if(t == 1){
			cout << 6000 * n << endl;
		}
		else if(t == 2){
			cout << 4000 * n << endl;
		}
		else if(t == 3){
			cout << 3000 * n << endl;
		}
		else if(t == 4){
			cout << 2000 * n << endl;
		}
	}

	return 0;
}



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

const string YES = "YES";
const string NO = "NO";

auto solve(std::string A, std::string B, std::string C){
    if((A[A.size()-1] == B[0]) && (B[B.size()-1] == C[0])) {
        return YES;
    }
    else {
        return NO;
    }
}

int main(){
    std::string A;
    std::cin >> A;
    std::string B;
    std::cin >> B;
    std::string C;
    std::cin >> C;
    auto result = solve(A, B, C);
    cout << result << endl;
    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
[解説AC]
塗っていくときにかかるコストはΣmax(0,h[i]-h[i-1])
k回まで高さを変えられる⇒k列は考えなくてよい(k列をその左と同じ高さにする)
残るのはn-k列のブロック
ある一列を残すと決めたとき、それにかかるコストはそれより前で残すと決めた列の高さに依存するため
dp[i][j] := i列目を残すとしたとき、i列目まででj列残す場合のコストの最小値とする
dp[i][j] = min(dp[i][j],dp[l][j-1] + max(0,h[i] - h[l])) (1<=l<i) (前回l列目を残し、今回i列目を残す場合)
ans = min(dp[i][n-k])
"""

n,k = LI()
h = [0] + LI()
dp = [[inf]*(n-k+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(1,n+1):
    for j in range(1,n-k+1):
        for l in range(i):
            dp[i][j] = min(dp[i][j],dp[l][j-1] + max(0,h[i]-h[l]))

ans = inf
for i in range(n+1):
    ans = min(ans,dp[i][n-k])
print(ans)

Measured memory_bytes: 47068
#include <algorithm>
#include <cstdio>
#include <list>
#include <vector>

typedef struct {
  size_t v;
  std::list<size_t> cs;
} elem_t;

void update(std::vector<elem_t> &nodes, size_t p) {
  elem_t &e = nodes[p];
  std::for_each(e.cs.begin(), e.cs.end(), [&](size_t pp) {
    nodes[pp].v += e.v;
    update(nodes, pp);
  });
}

int main() {
  size_t N, Q, a, b, p, x;
  std::vector<elem_t> nodes;

  scanf("%zu %zu", &N, &Q);

  for (size_t i = 0; i < N; i++) {
    elem_t e = { .v = 0 };
    nodes.push_back(e);
  }

  for (size_t i = 0; i < N - 1; i++) {
    scanf("%zu %zu", &a, &b);
    nodes[a - 1].cs.push_back(b - 1);
  }

  for (size_t i = 0; i < Q; i++) {
    scanf("%zu %zu", &p, &x);
    nodes[p - 1].v += x;
  }

  update(nodes, 0);

  std::for_each(nodes.begin(), nodes.end(), [](elem_t &e) {
    printf("%zu ", e.v);
  });

  printf("\n");
}

Measured memory_bytes: 22636
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right #func(リスト,値)
from heapq import heapify, heappop, heappush
from math import *

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))

N,P = mint()
A = lint()
even = len([a for a in A if a%2==0])
odd = N-even
if odd==0:
    print(0 if P else 2**N)
else:
    print(2**(N-1))

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

int main(void)
{
    char p;
    int count=0;
    int max=0;
    for(int i=0;i<3;i++)
    {
        cin >> p;
        if(p=='R')
        {
            count++;
        }
        else if(count>max)
        {
            max=count;
            count=0;
        }
    }
    if(count>max)
    {
        max=count;
    }
    cout << max << endl;
    return 0;
}

Measured memory_bytes: 3592
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define lli long long int
#define ulli unsigned long long int
#define ld long double
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define loop(i,a,b) for(lli i=a;i<b;i++)
#define initialize(array,size,value) for(lli i=0;i<size;i++) array[i]=value
#define couta(array,size) for(lli i=0;i<size;i++) cout<<array[i]<<" "
#define vl vector<lli>
#define vp vector< pair <lli,lli> >
#define sl set<lli>
#define msp multiset < pair < long long , long long > > S;
#define pll pair<lli, lli>
#define mll map<lli, lli>            //for( map<lli, lli>::iterator i=temp.begin();i!=temp.end();i++)cout<<i->fi<<" "<<i->se<<endl;
#define mvl map<lli, vl>
#define umll unordered_map<lli, lli>
#define vt vector<pair<lli, pll >  >
#define vf vector<pair<pll,pll > >
#define qu queue<lli>
#define pq priority_queue<lli>
#define dq deque <lli>
#define ptr vector<lli>::iterator
#define bs(array,x) binary_search(array.begin(),array.end(),x) // also valid for set and multiset
#define lb(array,x) lower_bound(array.begin(),array.end(),x)
#define ub(array,x) upper_bound(array.begin(),array.end(),x)
#define nobw(array,i,j) upper_bound(array.begin(), array.end(), j)-lower_bound(array.begin(), array.end(), i) //number of numbers between i & j
#define vc clear()
#define endl '\n'
#define sp system("pause");
#define INF 9223372036854775807
#define MINF -9223372036854775808
typedef tree<pll,null_type,less<pll>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
//string binary = bitset<32>(n).to_string(); 

int main() 
{ 

 	ios::sync_with_stdio(0);
    cin.tie(0);
  
    lli a,b,l,r;
    cin>>l>>r>>a>>b;
    if(l>r)swap(l,r);
    lli fi,la;
    if(l%a==0)fi=l/a;else fi=l/a+1;
    la=r/a;
    fi*=a,la*=a;
    //cout<<fi<<" "<<la<<endl;
    lli sum1=0,sum2=0,sum3=0;
    sum1+= (la-fi)/a+1;
    if(fi>la)sum1=0;
   
    if(l%b==0)fi=l/b;else fi=l/b+1;
    la=r/b;
    fi*=b,la*=b;
    //cout<<fi<<" "<<la<<endl;
    sum2+= (la-fi)/b+1;
    if(fi>la)sum2=0;
    lli c=(a*b)/__gcd(a,b);
    if(l%c==0)fi=l/c;else fi=l/c+1;
    la=r/c;
    fi*=c,la*=c;
    //cout<<fi<<" "<<la<<endl;
    sum3+= (la-fi)/c+1;
    if(fi>la)sum3=0;
   // cout<<sum1<<" "<<sum2<<" "<<sum3<<endl;
	cout<<r-l+1-sum1-sum2+sum3;    
    



	return 0; 
} 


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

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

	vector<pair<int, int>> p(N);
	for (int i = 0; i < N; i++) {
		int a, b;
		cin >> a >> b;
		p[i] = make_pair(a, b);
	}
	sort(p.begin(), p.end());

	int ans = 0;
	for (int i = 0; i < N; i++) {
		K -= p[i].second;
		if (K <= 0) {
			ans = p[i].first;
			break;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 1024
import numpy as np

H, W, K = map(int, input().split())
m = []
for _ in range(H):
  m.append([1 if s=="#" else 0 for s in input()])

m = np.array(m)
ans = 0

for h in range(2**H):
  for w in range(2**W):
    mcopy = m.copy()
    hcopy = h
    wcopy = w
    for i in range(H):
      if hcopy%2==1:
        mcopy[i,:] = 0
      hcopy = hcopy//2
    for i in range(W):
      if wcopy%2==1:
        mcopy[:,i] = 0
      wcopy = wcopy//2
    if mcopy.sum()==K:
      ans += 1

print(ans)

Measured memory_bytes: 27228
#include <iostream>
#include <iomanip>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <regex>
using namespace std;
using pii  = pair<int,int>;
using ll=long long;
using ld=long double;
#define pb push_back
#define mp make_pair
#define sc second
#define fr first
#define stpr setprecision
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define rep(i,n) for(ll i=0;i<(n);++i)
#define Rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define rRep(i,a,b) for(int i=a;i>=b;i--)
#define crep(i) for(char i='a';i<='z';++i)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define ALL(x) (x).begin(),(x).end()
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define endl '\n'
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b, a%b));}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
constexpr ll MOD=1000000007;
constexpr ll INF=1000000011;
constexpr ll MOD2=998244353;
constexpr ll LINF = 1001002003004005006ll;
constexpr ld EPS=10e-8;
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<typename T> istream& operator>>(istream& is,vector<T>& v){for(auto&& x:v)is >> x;return is;}
template<typename T,typename U> istream& operator>>(istream& is, pair<T,U>& p){ is >> p.first; is >> p.second; return is;}
template<typename T,typename U> ostream& operator>>(ostream& os, const pair<T,U>& p){ os << p.first << ' ' << p.second; return os;}
template<class T> ostream& operator<<(ostream& os, vector<T>& v){
  for(auto i=begin(v); i != end(v); ++i){
    if(i !=begin(v)) os << ' ';
    os << *i;
  }
  return os;
}
ll A,B,C,D,E,F,H,K,L,M,N,P,Q,R,W,X,Y,Z;
string S,T,U;
vector<ll> V;
int main(){
  cin >> S >> T >> U;
  cout << S[0] << T[0] << U[0] << endl;
}

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

const int mod=1e9+7;
ll power(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
ll inv(ll x){

    return power(x,mod-2);
}
vector<ll>g[200020];
int a[44444],b[44444];
vector<ll>v1,v2;
int main(){
    ll n,i,j,k,x,y,z,t,m;
    cin>>n>>m;
    double mi1=n/0.08,ma1=(n+1)/0.08,mi2=m/0.1,ma2=(m+1)/0.1;
    for(i=0;i<10000;i++){
        if(i>=mi1&&i<ma1&&i>=mi2&&i<ma2){cout<<i;return 0;}
    }
    cout<<-1;

}

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

using namespace std;
using ll = long long;

#define REP(i, n) for (ll i = 0; i < n; i++)
#define INF 9223372036854775807
#define all(x) (x).begin(), (x).end()

ll ts = 1000000007;

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

  ll a, b;
  cin >> a >> b;

  cout << (a + b - 3) / (a - 1) << "\n";
}

Measured memory_bytes: 256
using System;
using System.Linq;
 
class Amondai
{
    static void Main()
    {
        var num = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray();
        var max = num[0] < num[1] ? num[1] : num[0];
        var min = max == num[0] ? num[1] : num[0];
        var ans = -1L;
        var line1 = Console.ReadLine().ToCharArray();
        var line2 = Console.ReadLine().ToCharArray();
        if (line1[0] != line2[0])
        {
            Console.WriteLine(ans);
            return;
        }
        ans = GetS(max, min);
        if (max * min != ans)
        {
            var kankaku1 = ans / num[0];
            var kankaku2 = ans / num[1];
            var kankaku = GetS(kankaku1, kankaku2);
            for (long i = kankaku; i < ans; i += kankaku)
            {
                if (line1[i / kankaku1] != line2[i / kankaku2])
                {
                    ans = -1;
                    break;
                }
            }
        }
        Console.WriteLine(ans);
    }
 
    static long GetS(long max, long min)
    {
        var r = 0L;
        var a = max;
        var b = min;
        while ((r = max % min) != 0)
        {
            max = min;
            min = r;
        }
        return a * b / min;
    }
}

Measured memory_bytes: 13920
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define LLMAX (1ll << 60) - 1
#define INTMAX (1 << 30) - 1
#define MOD 1000000007 
#define NMAX 1000*100+1

#define numberOfSetBits(S) __builtin_popcount(S) // __builtin_popcountl(S) __builtin_popcountll(S)
#define MSET(x,y) memset(x,y,sizeof(x))
#define gcd(a,b) __gcd(a,b)
#define all(x)  x.begin(),x.end()
#define isOn(S, j) (S & (1 << j))
#define endl '\n'
#define setBit(S, j) (S |= (1 << j))
#define clearBit(S, j) (S &= ~(1 << j))
#define toggleBit(S, j) (S ^= (1 << j))
#define print(x)    for(auto it:x) cout<<it<<' '; cout<<endl;
#define printii(x)  for(auto it:x) cout<<it.F<<' '<<it.S<<'\t';  cout<<endl;
#define in(x,n)   for(int e=0;e<n;e++){ll y;cin>>y;x.pb(y);}

#define vi vector<ll>
#define vvi vector<vi>
#define ii pair<ll,ll>
#define pll pair<ll,ll>
#define vii vector<ii>
#define vvii vector<vii>
#define viii vector<pair<ii,ll>>
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define mc(a,b,c) mp(mp(a,b),c)
viii p,q;
viii edj;

struct DSU
{
    int n,x;
    vi p,r,sz;
    DSU(int N)
    {
        n=N;
        x=N-1;
        sz.assign(N,1);
        p.assign(N,0);
        r.assign(N,1);
        for(int i=0;i<N;i++)
            p[i]=i;
    }
    int findset(int i)
    {
        return (p[i]==i)?i:(p[i]=findset(p[i]));
    }
    bool issameset(int i,int j)
    {
        return findset(i)==findset(j);
    }
    void unionset(int i,int j)
    {
        int p1=findset(i);
        int p2=findset(j);
        if(p1!=p2)
        {
            x--;
            if(r[p1]>=r[p2])
            {
                p[p2]=p1;
                sz[p1]+=sz[p2];
                if(r[p1]==r[p2])
                    r[p1]++;
            }
            else
            {
                p[p1]=p2;
                sz[p2]+=sz[p1];
            }
        }
    }
    void disp()
    {
        for(int i=0;i<n;i++)
            cout<<p[i]<<' ';
        cout<<endl;
    }

    int getsize(int i){
        return sz[findset(i)];
    }
    int noofdisjointsets(){
        return x;
    }

};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,x,t,m,y,z;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x>>y;
        p.pb(mc(x,y,i));
        q.pb(mc(y,x,i));
    }
    sort(all(p));
    sort(all(q));
    for(int i=0;i<n-1;i++){
        edj.pb(mc(p[i+1].F.F-p[i].F.F,p[i+1].S,p[i].S));
        edj.pb(mc(q[i+1].F.F-q[i].F.F,q[i+1].S,q[i].S));
    }

    DSU foo(n);

    sort(all(edj));
    ll cost = 0;
    for(int i=0;(i<edj.size())&&(foo.noofdisjointsets());i++){
        x = edj[i].F.S;
        y = edj[i].S;
        if(!foo.issameset(x,y)){
            foo.unionset(x,y);
            cost+=edj[i].F.F;
        }
    }
    cout<<cost;
    




    return 0;
}

Measured memory_bytes: 13984
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>

using namespace std;

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

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

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

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(auto i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

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

//constant
const double EPS = 1e-5;
const double PI  = acos(-1.0);

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

#define PUTS(x) cout << (x) << endl;

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    const int MAX = 10000000;
    VI x(n, MAX);
    REP(i,m)
    {
        int a, b;
        cin>>a>>b;
        x[a - 1] = min(x[a - 1], b - 1);
    }
    int st = 0;
    int ans = 0;
    while(true)
    {
        int min_b = MAX;
        FOR(i,st,n)min_b = min(min_b, x[i]);
        if(min_b == MAX)break;
        ans++;
        st = min_b;
    }

    cout<<ans<<endl;
}

Measured memory_bytes: 640
N = int(input())
src = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for i in range(N)]
for u,v,w in src:
    u,v = u-1,v-1
    es[u].append((v,w))
    es[v].append((u,w))

visited = [0]*N
visited[0] = 1
ans = [0]*N
stack = [0]

while stack:
    v = stack.pop()
    for to,c in es[v]:
        if visited[to]: continue
        ans[to] = (ans[v]+c)%2
        visited[to] = 1
        stack.append(to)
print(*ans, sep='\n')

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

int n, m, k, s, fp;
vector<int> v[11];
bool p[11], bo[11];

void che() {
    for(int i = 1; i <= m; ++i) {
        if(p[i]) return;
    }
    ++fp;
}

void go(int i) {
    if(i == n + 1) {
        che();
        return;
    }
    for(int k = 0; k < 2; ++k) {
        bo[i] = k;
        go(i + 1);
        for(int j = 0; j < v[i].size(); ++j) {
            p[v[i][j]] ^= 1;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        cin >> k;
        for(int j = 1; j <= k; ++j) {
            cin >> s;
            v[s].push_back(i);
        }
    }
    for(int i = 1; i <= m; ++i) cin >> p[i];
    go(1);
    cout << fp << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include<math.h>
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
int main()
{
    int64_t N;
    cin >> N;
    vector<int64_t>vec(N);
    for (int64_t i=0; i<N; i++) {
        cin >> vec.at(i);
    }

    int64_t sum_ = 0;
    int64_t kizyun = 0;
    for (int64_t i=0; i<N; i++) {
        int64_t num = vec[i];
        if (kizyun > num) {
            sum_ += (kizyun - num);
        } else {
            kizyun = num;
        }
    }

    cout << sum_ << endl;
    return 0;
}

Measured memory_bytes: 4836
using System.IO;
using System.Text;
using System;
   
   
namespace AOJ
{
    class Scanner : StringReader
    {
        string _currentWord;
   
        public Scanner(string source) : base(source)
        {
            ReadNextWord();
        }
   
        private void ReadNextWord()
        {
            StringBuilder sb = new StringBuilder();
            do
            {
                var next = Read();
                if (next < 0)
                    break;
                var nextChar = (char)next;
                if (char.IsWhiteSpace(nextChar))
                    break;
                sb.Append(nextChar);
            } while (true);
            while ((Peek() >= 0) && (char.IsWhiteSpace((char)Peek())))
                Read();
            _currentWord = sb.Length > 0 ? sb.ToString() : null;
        }
   
        public bool HasNextInt()
        {
            if (_currentWord == null)
                return false;
            int dummy;
            return int.TryParse(_currentWord, out dummy);
        }
   
        public int NextInt()
        {
            try
            {
                return int.Parse(_currentWord);
            }
            finally
            {
                ReadNextWord();
            }
        }
   
        public bool HasNextDouble()
        {
            if (_currentWord == null)
                return false;
            double dummy;
            return double.TryParse(_currentWord, out dummy);
        }
   
        public double NextDouble()
        {
            try
            {
                return double.Parse(_currentWord);
            }
            finally
            {
                ReadNextWord();
            }
        }
   
        public bool HasNext()
        {
            return _currentWord != null;
        }
    }
   
    class Program
    {
        public static int[] InsertionSort(int[] unsorted)
        {
            var list = new int[unsorted.Length];
            unsorted.CopyTo(list, 0);
            Console.WriteLine(string.Join(" ", Array.ConvertAll(unsorted, s => s.ToString())));
            for (var i = 1; i < list.Length; i++)
            {
                var key = list[i];
                int j;
                for (j = i - 1; j >= 0 && list[j] > key; j--)
                {
                    list[j + 1] = list[j];
                }
                list[j + 1] = key;
                Console.WriteLine(string.Join(" ", Array.ConvertAll(list, s => s.ToString())));
            }
            return list;
        }
   
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            Scanner s = new Scanner(Console.ReadLine());
   
            var unsorted = new int[n];
            for (int i=0; s.HasNext(); i++)
            {
                unsorted[i] = s.NextInt();
            }
            InsertionSort(unsorted);
   
   
        }
    }
}

Measured memory_bytes: 9424
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<functional>
#include<map>
#include<cstdlib>
#include<complex>
#include<numeric>
#include<set>

using namespace std;
using Int = long long;
Int INF = 1LL << 60;
const Int MOD = 1000000007;

struct city {
	Int pref;//県番号
	Int year;
	Int num;//県の内何番目か
	Int id;//入力番号

};


int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	Int N, M;
	cin >> N >> M;

	vector<city> cities(M);
	for (Int i = 0; i < M; i++) {
		cin >> cities[i].pref >> cities[i].year;
		cities[i].id = i;
	}

	//yearでsort
	sort(cities.begin(), cities.end(), [](const city& x, const city& y) {return x.year < y.year; });

	vector<Int> Pre(100001);
	for (Int i = 0; i < M; i++) {
		Pre[cities[i].pref]++;
		cities[i].num = Pre[cities[i].pref];
	}

	//idでsort
	sort(cities.begin(), cities.end(), [](const city& x, const city& y) {return x.id < y.id; });

	for (Int i = 0; i < M; i++) {
		printf("%06lld", cities[i].pref);
		printf("%06lld\n", cities[i].num);
	}
}

Measured memory_bytes: 5504
import java.util.*;
 
public class Main {
	public static void main(String[] args) throws Exception{
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
        int B = sc.nextInt();
        int m = sc.nextInt();
        int[] a = new int[A];
        int[] b = new int[B];
        for(int i = 0; i < A; i++){
        	a[i] = sc.nextInt();
        }
        for(int i = 0; i < B; i++){
        	b[i] = sc.nextInt();
        }
        int dis = Integer.MAX_VALUE;
        for(int i = 0; i < m; i++){
        	int x = sc.nextInt();
            int y = sc.nextInt();
            int c = sc.nextInt();
            int disnow = a[x - 1] + b[y - 1] - c;
            dis = Math.min(dis, disnow);
        }
        Arrays.sort(a);
        Arrays.sort(b);
        System.out.println(Math.min((a[0] + b[0]), dis));
	}
}

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

// #undef DEBUG  // Uncomment this line to forcefully disable debug print.
#if DEBUG
template <typename T>
void debug(const T& value) {
  std::cerr << value;
}
template <typename T, typename... Ts>
void debug(const T& value, const Ts&... args) {
  std::cerr << value << ", ";
  debug(args...);
}
#define dbg(...)                        \
  do {                                  \
    cerr << #__VA_ARGS__ << ": ";       \
    debug(__VA_ARGS__);                 \
    cerr << " (L" << __LINE__ << ")\n"; \
  } while (0)
#else
#define dbg(...)
#endif

void read_from_cin() {}
template <typename T, typename... Ts>
void read_from_cin(T& value, Ts&... args) {
  std::cin >> value;
  read_from_cin(args...);
}
#define in(type, ...) \
  type __VA_ARGS__;   \
  read_from_cin(__VA_ARGS__);

template <typename T>
void write_to_cout(const T& value) {
  std::cout << value << '\n';
}
template <typename T, typename... Ts>
void write_to_cout(const T& value, const Ts&... args) {
  std::cout << value << ' ';
  write_to_cout(args...);
}
#define out(...) write_to_cout(__VA_ARGS__);

#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

using ll = long long;

template <typename T>
using V = std::vector<T>;
template <typename T>
using VV = V<V<T>>;

using namespace std;

template <typename T>
class BIT {
 public:
  BIT(int n) : v_(n) {}
  T Sum(int i) const {
    T ret = 0;
    while (i >= 0) {
      ret += v_[i];
      i = (i & (i + 1)) - 1;
    }
    return ret;
  }
  T Get(int i) const { return Sum(i) - Sum(i - 1); }
  void Add(int i, T v) {
    while (i < v_.size()) {
      v_[i] += v;
      i |= i + 1;
    }
  }

 private:
  std::vector<T> v_;
};

using P = pair<int, int>;

struct Query {
  int i, l, r;
};

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

  in(int, N, M, Q);

  V<P> trains;
  rep(i, M) {
    in(int, L, R);
    trains.push_back({L - 1, R - 1});
  }
  sort(all(trains), [](const P& a, const P& b) { return a.second < b.second; });

  V<Query> queries;
  rep(i, Q) {
    in(int, p, q);
    queries.push_back({i, p - 1, q - 1});
  }
  sort(all(queries), [](const Query& a, const Query& b) { return a.r < b.r; });

  V<int> ans(Q);
  BIT<int> bit(N);
  auto ti = trains.begin();
  auto qi = queries.begin();
  rep(r, N) {
    for (; ti != trains.end() && ti->second <= r; ++ti) {
      bit.Add(ti->first, 1);
    }
    for (; qi != queries.end() && qi->r <= r; ++qi) {
      ans[qi->i] = bit.Sum(qi->r) - bit.Sum(qi->l - 1);
    }
  }
  rep(i, Q) out(ans[i]);
}


Measured memory_bytes: 7400
#include <iostream>

using namespace std;

class Array
{
	int* dataArray;
	int arraySize;

public:
	Array(int arraySize)
	{
		this->arraySize = arraySize;

		dataArray = new int[arraySize];

		for (int i = 0; i < arraySize; i++)
		{
			dataArray[i] = 0;
		}
	}

	~Array()
	{
		delete[] dataArray;
	}

	int& operator [](int n)
	{
		return dataArray[n];
	}

	Array(const Array& ob)
	{
		this->arraySize = ob.arraySize;
		
		for (int i = 0; i < arraySize; i++)
		{
			this->dataArray[i] = ob.dataArray[i];
		}
	}

	void ShowArray();

	void InsertionSort();
};

//昇順に挿入ソートする
void Array::InsertionSort()
{
	for (int i = 1; i < arraySize; i++)
	{
		int target = i;

		while (target >= 1 && dataArray[target -1] > dataArray[target])
		{			
			int temp = dataArray[target];

			dataArray[target] = dataArray[target - 1];
			dataArray[target - 1] = temp;

			target--; 
		}

		ShowArray();
	}
}

//要素間は空白で区切り、配列の中身を表示する
void Array::ShowArray()
{
	for (int i = 0; i < arraySize; i++)
	{
		if (i > 0)
		{
			cout << " ";
		}

		cout << dataArray[i];
	}
	cout << endl;
}

int main()
{	
	//■入力ストリームからデータ取得
	int N;
	cin >> N;

	Array array1(N);

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

	//■配列に格納されたデータの初期状態を表示
	array1.ShowArray();

	//■昇順に挿入ソート
	array1.InsertionSort();

	return 0;
}


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

int main(){
	string a,b,ans;
  	cin>>a>>b;
  	if(a.size()>b.size()){
      cout<<"GREATER"<<endl;return 0;}
  	else if(a.size()<b.size()){
    	cout<<"LESS"<<endl;return 0;}
	int an,bn,i=0;
  	while(i<a.size()){
      an=(int)(a[i]-'0');
      bn=(int)(b[i]-'0');
      if(an>bn){cout<<"GREATER"<<endl;return 0;}
      else if(an<bn){cout<<"LESS"<<endl;return 0;}
      i++;
    }
  	cout<<"EQUAL"<<endl;
  	return 0;
}


Measured memory_bytes: 256
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
using E = System.Linq.Enumerable;
 
class Program
 {
        static int R;
        static int C;
        static int[] S;
        static int[] G;
        static string[] map;
        static int[,] ans;
        static void Main(string[] args)
        {
          //入力を受け取る
          var N  = int.Parse(Console.ReadLine());
          var A = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
          
          var adjast = Math.Round(A.Average(),MidpointRounding.AwayFromZero);
          var ans = 0L;
          for(int i = 0; i < N ; i++){
            ans += (int) Math.Pow(A[i]-adjast,2);
          }
          
          Console.WriteLine(ans);
          
        }
}







Measured memory_bytes: 13396
/*
Author : Xinyuan
*/
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < n; i++)
#define all(x) (x).begin(), (x).end()
#define INF 1000000007
#define mod 1005
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef long long int ll;
ll powmod(ll a, ll b) {
    ll res = 1;
    a %= mod;
    assert(b >= 0);
    for (; b; b >>= 1) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}
int nxt() {
    int x;
    scanf("%d", &x);
    return x;
}

int main() {
    int n = nxt(), w = nxt();
    vector<ll> memo(w + 1, 0);
    REP(i, n) {
        int weight = nxt(), v = nxt();
        for (int j = w; j >= weight; j--) memo[j] = max(memo[j], memo[j - weight] + (ll)v);
    }
    sort(memo.rbegin(), memo.rend());
    printf("%lld\n", memo[0]);
    return 0;
}


Measured memory_bytes: 1024
using System;

class Program
{
    static void Main(string[] args)
    {
        var input = Console.ReadLine().Split(' ');
        var num1 = Convert.ToInt32(input[0]);
        var num2 = Convert.ToInt32(input[1]);

        if (num1 % 2 != 0 && num2 % 2 != 0) Console.WriteLine("Yes");
        else Console.WriteLine("No");
    }
}

Measured memory_bytes: 11220
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define INF 1000000009
//#define INF 9223372036854775807
typedef long long ll;
#define REP(i,n) for(int i=0;i<(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define rollcall cout<<"I'm Sucu."<<endl;
#define YES(s) s?cout << "YES" << endl:cout << "NO" << endl
#define Yes(s) s?cout << "Yes" << endl:cout << "No" << endl
#define Taka(s) s?cout << "Takahashi" << endl:cout << "Aoki" << endl
#define out(s,t,u) s?cout << t << endl:cout << u << endl
#define int ll
#define Endl endl


signed main(){
    int N,M,Ans=0;
    int a[21500],b[21500],c[21500];
    int d[104][104];
    REP(i,104){
        REP(j,104){
            d[i][j]=INF;
        }
    }
    REP(i,104){d[i][i]=0;}
    cin >> N >> M;
    REP(i,M){
        cin >> a[i] >> b[i] >> c[i];
        a[i]--;b[i]--;
        d[a[i]][b[i]]=c[i];
        d[b[i]][a[i]]=c[i];
    }
    REP(k,N){
        REP(i,N){
            REP(j,N){
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
    
   // REP(i,N){REP(j,N){cout << d[i][j] << " ";}cout << endl;}cout << endl;
    
    
    int co=0;
    REP(k,M){
        co=1;
        REP(i,N){
            REP(j,N){
                if(d[i][a[k]]+c[k]+d[b[k]][j]==d[i][j]){
                    co=0;
                }
            }
        }
        if(co==1){
            Ans++;
           // cout << a[k]+1 <<" "<< b[k]+1 <<" "<< d[a[k]][b[k]]<< endl;
        }
    }
    cout << Ans << endl;
    return 0;
}   



Measured memory_bytes: 384
import java.util.Scanner;

class Main {

    static Scanner sc;
    static int[] input;
    static long count;
    static final int INF = Integer.MAX_VALUE;

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

        input = new int[n];
        for(int i = 0; i < n; i++) {
            input[i] = sc.nextInt();
        }
        MergeSort(0, n);
        System.out.println(count);
    }

    static void MergeSort(int left, int right) {
        if(left+1 < right) {
            int mid = (left + right) / 2;
            MergeSort(left, mid);
            MergeSort(mid, right);
            Merge(left, mid, right);
        }
    }

    static void Merge(int left, int mid, int right) {
        int n1 = mid - left;
        int n2 = right - mid;
        int[] L = new int[n1+1];
        int[] R = new int[n2+1];

        for(int i = 0; i < n1; i++)
            L[i] = input[left + i];
        for(int i = 0; i < n2; i++)
            R[i] = input[mid + i];

        L[n1] = R[n2] = INF;

        int i = 0; int j = 0;
        for (int k = left; k < right; k++) {
            if(L[i] <= R[j]) {
                input[k] = L[i];
                i++;
            } else {
                input[k] = R[j];
                j++;
                count += n1 - i;
            }
        }
    }
}



Measured memory_bytes: 102728
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>

#define reps(i,s,n) for(int (i) = (s); (i) < (n); (i)++)
#define rep(i,n) reps(i,0,n)
using namespace std;
using ll = long long;

int main(){
    int n;
    int num;
    cin >> n;
    vector<int> a(1e6+10,0);
    int cnt_minus = 0;
    rep(i,n){ 
        cin >> num;
        if(num == 0){
            cnt_minus++;
            a[num]++;
            a[num+1];
        }else{
            a[num-1]++;
            a[num]++;
            a[num+1]++;
        }
    }

    int ans = cnt_minus;
    rep(i,1e6+1){
        ans = max(ans,a[i+1]); 
    }
    cout << ans << endl;

    return 0;
}

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

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

  if (r - l + 1 >= 2019) {
    cout << 0 << endl;
    return 0;
  }

  int64_t ans = 2019;
  for (int j = l + 1; j <= r; j++) {
    for (int i = l; i < j; i++) {
      ans = min(ans, int64_t(i) * j % 2019);
      if (ans == 0) break;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
def BubbleSort(lists, num):
  cards = lists[:]
  for i in xrange(num):
    for j in xrange(num - 1, i, -1):
      if cards[j].value < cards[j - 1].value:
        cards[j], cards[j - 1] = cards[j - 1], cards[j]
  return cards

def SelectionSort(lists, num):
  cards = lists[:]
  for i in xrange(num):
    minj = i
    for j in xrange(i, num):
      if cards[j].value < cards[minj].value:
        minj = j
    cards[i], cards[minj] = cards[minj], cards[i]
  return cards

class Card(object):
  """docstring for Card"""
  def __init__(self, arg):
    self.mark = arg[0]
    self.value = int(arg[1])

num = int(raw_input())
inputs = raw_input().split()
cards = [Card(inputs[x]) for x in xrange(num)]

bubble_ans = ""
bubble_cards = BubbleSort(cards, num)
for x in bubble_cards:
  bubble_ans += x.mark + str(x.value) + " "
print bubble_ans.rstrip()
print "Stable"

select_ans = ""
select_cards = SelectionSort(cards, num)
for x in select_cards:
  select_ans += x.mark + str(x.value) + " "
print select_ans.rstrip()
flag = True
for x in xrange(num):
  if bubble_cards[x].mark != select_cards[x].mark:
    flag = False
    break
print "Stable" if flag else "Not stable"

Measured memory_bytes: 6520
pub struct Poper<'a> {
	iter: std::str::SplitWhitespace<'a>,
}

impl<'a> Poper<'a> {
	pub fn new(iter: std::str::SplitWhitespace) -> Poper {
		Poper { iter: iter }
	}
	pub fn read<T: std::str::FromStr>(&mut self) -> T
	where
		<T as std::str::FromStr>::Err: std::fmt::Debug,
	{
		self.iter.next().unwrap().parse().unwrap()
	}
}

fn main() {
	let input = {
		use std::io::Read;
		let mut s = String::new();
		std::io::stdin().read_to_string(&mut s).unwrap();
		s
	};
	let mut iter = Poper::new(input.split_whitespace());

	let mut n: i32 = iter.read();
	let d: i32 = iter.read();

	let mut c: u32 = 0;

	let d = 2 * d + 1;

	while n >= d {
		c += 1;
		n -= d;
	}
	if n > 0 {
		c += 1;
	}


	println!("{}", c);
}


Measured memory_bytes: 4352
#include <iostream>
#include <iomanip>
#include <string>
#include <limits.h>
#include <math.h>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <cstdlib>
#include <typeinfo>

using namespace std;

int ctoi(char c) {
  if (c >= '0' && c <= '9') {
    return c - '0';
  }
  return 0;
}

int main(int argc, char* argv[]){
  string input, output;
  cin >> input;
  // cout << input[1] << endl;
  char op[3];
  output = input[0];
  int count = 0, diff;
  int a[4], choice[7];
  for (int i=0; i< 4; i++){
    a[i] = ctoi(input[i]);
  }
  // cout << a[0] << endl;
  diff = 7 - a[0];
  choice[0] = a[1] + a[2] + a[3];
  // cout << choice[0];
  choice[1] = a[1] + a[2] - a[3];
  choice[2] = -a[1] + a[2] + a[3];
  choice[3] = a[1] - a[2] + a[3];
  choice[4] = a[1] - a[2] - a[3];
  choice[5] = -a[1] + a[2] - a[3];
  choice[6] = -a[1] - a[2] + a[3];
  if(diff == choice[0]){
      op[0] = '+';
      op[1] = '+';
      op[2] = '+';
      // cout << "+++" << endl;
  }else if(diff == choice[1]){
      op[0] = '+';
      op[1] = '+';
      op[2] = '-';
  }else if(diff == choice[2]){
      op[0] = '-';
      op[1] = '+';
      op[2] = '+';
  }else if(diff == choice[3]){
      op[0] = '+';
      op[1] = '-';
      op[2] = '+';
  }else if(diff == choice[4]){
      op[0] = '+';
      op[1] = '-';
      op[2] = '-';
  }else if(diff == choice[5]){
      op[0] = '-';
      op[1] = '+';
      op[2] = '-';
  }else if(diff == choice[6]){
      op[0] = '-';
      op[1] = '-';
      op[2] = '+';
  }
  for(int i=0; i<3; i++){
    output += op[i];
    output += input[i+1];
  }
  cout << output << "=7" << endl;
  return 0;
}


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

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

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e16
#define mod 1000000007

ll n;
ll a[200010];
ll sum[200010];

int main(){
  cin>>n;
  rep(i,n)cin>>a[i];
  rep(i,n)sum[i+1]=sum[i]+a[i];
  ll res=INF;
  repl(i,2,n-1){
    vector<ll> vs[2][2];
    {
      ll lb=1,ub=i;
      while(ub-lb>1){
        ll mid=(lb+ub)/2;
        if(sum[mid]<=sum[i]-sum[mid])lb=mid;
        else ub=mid;
      }
      vs[0][0].push_back(sum[lb]);
      vs[0][0].push_back(sum[i]-sum[lb]);
      if(lb<i-1){
        vs[0][1].push_back(sum[lb+1]);
        vs[0][1].push_back(sum[i]-sum[lb+1]);
      }
    }
    {
      ll lb=i+1,ub=n;
      while(ub-lb>1){
        ll mid=(lb+ub)/2;
        if(sum[mid]-sum[i]<sum[n]-sum[mid])lb=mid;
        else ub=mid;
      }
      vs[1][0].push_back(sum[lb]-sum[i]);
      vs[1][0].push_back(sum[n]-sum[lb]);
      if(lb<n-1){
        vs[1][1].push_back(sum[lb+1]-sum[i]);
        vs[1][1].push_back(sum[n]-sum[lb+1]);
      }
    }
    rep(j,2)rep(k,2){
      if(vs[0][j].size()==2&&vs[1][k].size()==2){
        minch(res,max(*max_element(all(vs[0][j])),*max_element(all(vs[1][k])))-min(*min_element(all(vs[0][j])),*min_element(all(vs[1][k]))));
      }
    }
  }
  cout<<res<<endl;
  return 0;
}


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

#define i64 long long int
#define ran 101101

int n, m, k;
int p[ran], sz[ran], det[ran];

int get_p(int x) { 
	return (p[x]<0) ? x : (p[x] = get_p(p[x]));
}

int main() {
	scanf("%d%d%d", &n, &m, &k);
	memset(p, -1, sizeof p);
	memset(det, 0, sizeof p);
	for(int i=0;i<m;i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		
		det[x]++; det[y]++;
		int a = get_p(x), b = get_p(y);
		if(a!=b) p[a] = b;
	}
	for(int i=1;i<=n;i++)
		sz[get_p(i)]++;
	
	for(int i=0;i<k;i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		
		int a = get_p(x), b = get_p(y);
		if(a==b) {
			det[x]++;
			det[y]++;
		}
	}
	for(int i=1;i<=n;i++)
		printf("%d%c", sz[get_p(i)] - 1 - det[i], i<n?' ':'\n');
	
	return 0;
}

Measured memory_bytes: 2304
import sys
from sys import exit
from math import gcd, factorial, ceil, floor, sqrt
from bisect import bisect_left, bisect_right
from copy import deepcopy
from heapq import heapify, heappop, heappush
from itertools import permutations, combinations, product, accumulate
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(10**7)

ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(map(int, input().split()))

N, X, M = mi()

if X == 0:
    print(0)
    sys.exit()
if M == 1 or N == 1:
    print(X)
    sys.exit()

ans = 0
ls = []

s = set()
num = X
cur = 0
f = 0
while not num in s:
    s.add(num)
    cur += 1
    ls.append(num)
    if cur == N:
        f = 1
        break

    num = num**2%M
    if num == 0:
        f = 1
        break
    if num == 1:
        f = 2
        break
if f == 1:
    print(sum(ls[:min(cur, N)]))
    sys.exit()
m = [0] + list(accumulate(ls))
if f == 2:
    print(m[-1] + (N-len(ls)))
    sys.exit()

i = ls.index(num)
b = ls[i:]

a = (N-i)//len(b)

ind = (N-i) - a*len(b)

print(sum(ls[:i]) + sum(b)*a + sum(b[:ind]))

Measured memory_bytes: 16412
import java.util.*;
import java.lang.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int i=1;
		for(;;) {
			if(a<b*i+c*(i+1))break;
			i++;
		}
		System.out.println(i-1);
	}
}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define endl        '\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000001
#define r(i,a,b)    for(i=a;i<b;i++)
#define ra(i,a,b)   for(i=a;i<=b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define ss          set<ll int>
using namespace std;
 
#define N 1000000
#define M 100000000

struct unit {
  ll int a[N];  
};

ll fact (ll int x)
{if(x==1 || x==0)return 1;
else return x*fact(x-1);}

ll power(ll int x,ll int n)
{if(n==0)return 1;
else if(n%2 == 0)return power(x*x,n/2);
else return x*power(x*x,(n-1)/2);}

bool cmp (const pii&a,const pii&b)
{ return((a.F-a.S) > (b.F-b.S));
/*if(a.S<=b.S){if(a.S==b.S)return a.F<b.F;else return a.S<b.S;}
else return a.S<b.S;*/}


int main()
{
    cin.tie(0), cin.sync_with_stdio(0), cout.tie(0), cout.sync_with_stdio(0);
    ll i,j,k,l,m,n;
    string s1=" ";
    string s2=" ";
  cin>>n;
  cin>>s1;
  if(sz(s1)<=n)
    cout<<s1;
  else{
    for(i=0;i<n;i++)
    cout<<s1[i];
    for(i=0;i<3;i++)
    cout<<".";
	/*for(i=0;i<n;i++)
      s2[i]+=s1[i];
    for(i=n;i<n+3;i++)
      s2[i]+='.';*/
    //cout<<s2;
  }
}



Measured memory_bytes: 3656
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int a [] = new int [N];
        for (int i = 0 ; i < N ; i++ ) {
            a[i] = sc.nextInt();
        }
        int count = 0;
        int temp = 1;
        for (int i = 0 ; i < N ; i++ ) {
             temp = a[temp - 1];
             count++;
             if (temp == 2) {
                 System.out.println(count);
                 return;
             }
        }
        System.out.println(-1);

    }

}

Measured memory_bytes: 50184
#include<bits/stdc++.h>
using namespace std;
#define int long long
int knapsack(int v[],int wt[],int n,int w){
	int maxvalue = n*1000;
	int dp[n+1][maxvalue+1];
	for(int i=0;i<=maxvalue;i++){
		dp[1][i]=INT_MAX;
	}
	dp[1][0]=0;
	dp[1][v[1]]=wt[1];
	for(int i=2;i<=n;i++){
		for(int	j=0;j<=maxvalue;j++){
			dp[i][j]=dp[i-1][j];//not selecting current item implies finding next item with value j
			if(v[i]>j){
				continue;
			}
			dp[i][j]=min(dp[i][j],wt[i]+dp[i-1][j-v[i]]);
		}
	}
	int ans=0;
	for(int x=0;x<=maxvalue;x++){
		if(dp[n][x]<=w){
			ans=x;
		}
	}
	return ans;
}
signed main(){
	int n,w;
	cin>>n>>w;
	int wt[n];
	int v[n];
	for(int i=1;i<=n;i++){
		cin>>wt[i];
		cin>>v[i];
	}
	cout<<knapsack(v,wt,n,w)<<endl;
	return 0;
}

Measured memory_bytes: 78336