akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

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


// std::vector Declaration
template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
   return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

// std::vector Initialization
template<typename T>
void fill_all(T& arr, const T& v) { arr = v; }
template<typename T, typename U>
void fill_all(T& arr, const U& v) { for (auto& i : arr) fill_all(i, v); }

// std::vector Debug
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
   os << "[";
   bool a = 1;
   for (auto e : v ) {
      os << (a ? "" : " "); 
      os << e;
      a = 0;
   }
   os << "]";
   return os;
}

// std::pair Debug
template<typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
   os << "(" << p.first << " " << p.second << ")";
   return os;
}

// std::set Debug
template<typename T>
ostream& operator<<(ostream& os, const set<T>& st) {
   os << "{";
   bool a = 1;
   for (auto e : st) {
      os << (a ? "" : " ");
      os << e;
      a = 0;
   }
   os << "}";
   return os;
}

// std::map Debug
template<typename T, typename U>
ostream& operator<<(ostream& os, const map<T, U>& mp) {
   os << "{";
   bool a = 1;
   for (auto e : mp) {
      os << (a ? "" : " ");
      os << e.first << ":" << e.second;
      a = 0;
   }
   os << "}";
   return os;
}

// std::tuple Debug
template<int N,class Tuple>
void out(ostream &os,const Tuple &t){}
template<int N,class Tuple,class H,class ...Ts>
void out(ostream &os,const Tuple &t){
   if(N)os<<" ";
   os<<get<N>(t);
   out<N+1,Tuple,Ts...>(os,t);
}
template<class ...Ts>
ostream& operator<<(ostream &os, const tuple<Ts...> &t){
   os<<"(";
   out<0,tuple<Ts...>,Ts...>(os,t);
   os<<")";
   return os;
}

// Debug
#define DUMP(x) cout<<#x<<" = "<<(x)<<endl

struct edge { int to, cost; };

const LL LINF = 1LL<<60;
const int IINF = 1<<30;
const LL MOD = 1e9+7;

int main()
{
   LL N; cin >> N;
   LL ans = 0;
   for (LL k = 1; k*k <= N+10; ++k) {
      if (N % k == 0) {
         LL m = N / k - 1;
         if (k <= m-1) {
            ans += m;
         }
      }
   }
   cout << ans << endl;

   return 0;
}


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


int main() {

    while(true)
    {
        //?????????????????°??\???
        int cards[2];
        cin >> cards[0] >> cards[1];
        //0??????????????????
        if(cards[0] == 0)
            break;
        //????????????????????¨??????????¨???\???
        int taro[cards[0]], hanako[cards[1]];
        int t_sum=0, h_sum=0, gap=0;
        
        for(int i = 0; i<cards[0];i++)
        {
            cin >> taro[i];
            t_sum+=taro[i];
        }
        for(int i=0;i<cards[1];i++)
        {
            cin >> hanako[i];
            h_sum+=hanako[i];
        }
        //????¨???????
        gap = h_sum - t_sum;
        if(gap%2 != 0) //???????????°??§????????¨???????????????
        {
            cout << -1 << endl;
        }
        else
        {
            gap /= 2;//???????????????????????????????????????
        
            int output[2] = {-1,-1};//??????????????°???
            int out_sum = 300;//??°?????????
            for(int i = 0;i<cards[0];i++)
                for(int j = 0;j<cards[1];j++)
                {
                    if(hanako[j] - taro[i] == gap && hanako[j] + taro[i] < out_sum)
                    {
                        output[0] = taro[i];
                        output[1] = hanako[j];
                        out_sum = output[0] + output[1];
                    }
                
                }
            if(output[0] == -1)
                cout << -1 << endl;
            else
                cout << output[0] << " " << output[1] << endl;
        }
        
    }
    return 0;
}

Measured memory_bytes: 3088
//region #include <cp_helper>
#include <algorithm>
#include <array>
#include <bitset>
#include <cstring>
#include <cmath>
#include <climits>
#include <deque>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <array>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define io() ios_base::sync_with_stdio(false); cin.tie(nullptr)
#define ll long long
#define ull unsigned long long
#define ii pair<int, int>
#define vi vector<int>
#define vvi vector<vi>
#define vl vector<ll>
#define vll vector< pair<ll, ll> >
#define vvl vector<vl>
#define vii vector<ii>
#define all(a) a.begin(), a.end()
#define qsort(a) sort(all(a))
#define qsortd(a) sort(all(a), greater<>())
#define qsortf(a, f) sort(all(a), f)
#define pb(n) push_back(n)
#define eb(n) emplace_back(n)
#define pp(a, b) emplace_back(make_pair(a, b))
#define fori(i, n) for (ll i=0; i<n; ++i)
#define foris(i, a, b) for (ll i=a; i<b; ++i)
#define ford(i, n) for (ll i=n; i>=0; --i)
#define fords(i, a, b) for (ll i=a; i>=b; --i)
#define forr(i, a) for (auto &i : a)
#define umap unordered_map
#define nl '\n'
#define fileio(in, out) freopen(in, "r", stdin); freopen(out, "w", stdout)
const int mod = 1000000007;
//endregion

int main() {
    io();
    int n, a;
    cin >> n;
    foris (i, 1, 10) {
        a = n/i;
        if (a*i != n) continue;
        if (1 <= a and a <= 9) {
            cout << "Yes";
            return 0;
        }
    }
    cout << "No";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000
#define MOD 1000000007
#define all(v) v.begin(),v.end()
#define pb push_back
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int kaijo[200010];
struct edge{int to,cost;};
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}
bool prime(int a){
	if(a==1)return false;
	for(int i=2;i*i<=a;i++){
		if(a%i==0)return false;
	}
	return true;
}
bool kosa(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy){//線分の交差判定
	double ta=(cx-dx)*(ay-cy)+(cy-dy)*(cx-ax);
	double tb=(cx-dx)*(by-cy)+(cy-dy)*(cx-bx);
	double tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx);
	double td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx);
	return tc*td<0&&ta*tb<0;
}
void init_fact(int n){
	kaijo[0]=1;
	for(int i=1;i<=n;i++){
		kaijo[i]=kaijo[i-1]*i;
		kaijo[i]%=MOD;
	}
}
int modpow(int a,int b){
	if(b==0)return 1;
	if(b%2)return modpow(a,b-1)*a%MOD;
	int memo=modpow(a,b/2);
	return memo*memo%MOD;
}
int comb(int a,int b){
	if(b>a)return 0;
	if(a==b)return 1;
	return kaijo[a]*modpow(kaijo[a-b],MOD-2)%MOD*modpow(kaijo[b],MOD-2)%MOD;
}
int g(int x){
	x=modpow(x,MOD-2);
	return x;
}
int n,b[110],a[110],ans;
signed main(){
	cin>>n;
	rep(i,n-1)cin>>b[i];
	rep(i,n){
		if(i==0)a[i]=b[i];
		else if(i==n-1)a[i]=b[i-1];
		else a[i]=min(b[i],b[i-1]);
	}
	rep(i,n)ans+=a[i];
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
using System;
using System.Text;
using System.Collections.Generic;
class Program
{
    //static List<string> str = new List<string>();
    static void Main(string[] args)
    {
        // ���̓t�F�[�Y
        string S = Console.ReadLine();
        string T = Console.ReadLine();

        // S�𓪂���u�����Ă���
        int len = S.Length;
        Dictionary<char, char> dicS = new Dictionary<char, char>();
        Dictionary<char, char> dicT = new Dictionary<char, char>();
        bool canSwap = true;
        for (int i = 0; i < len; i++)
        {
            // S[i]��T[i]
            if(!dicS.ContainsKey(S[i]))
            {
                dicS.Add(S[i], T[i]);
            }
            else
            {
                if(dicS[S[i]].CompareTo(T[i]) != 0)
                {
                    canSwap = false;
                    break;
                }
            }

            if (!dicT.ContainsKey(T[i]))
            {
                dicT.Add(T[i], S[i]);
            }
            else
            {
                if (dicT[T[i]].CompareTo(S[i]) != 0)
                {
                    canSwap = false;
                    break;
                }
            }
        }
        //Console.WriteLine(sb.ToString());
        //Console.WriteLine(T);
        if (canSwap)
        {
            // �u�������ł���
            Console.WriteLine("Yes");
        }
        else
        {
            Console.WriteLine("No");
        }
    }

    //static void swap(ref StringBuilder S, char a, char b)
    //{
    //    S.Replace(a, '*');
    //    S.Replace(b, a);
    //    S.Replace('*', b);
    //}

}

Measured memory_bytes: 13268
n = int(raw_input())
graph = [[0 for i in xrange(n)] for j in xrange(n)]

for i in xrange(n):
	fffff = map(int,raw_input().split())
	y = fffff[0] - 1
	for j in xrange(fffff[1]):
		graph[y][fffff[j + 2] - 1] = 1
		
for i in xrange(n):
	print " ".join(map(str, graph[i]))

Measured memory_bytes: 6412
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq as hq
import itertools as its
import operator as op


# globals
inf = float('inf')
N = 0


def set_inputs():
    global N
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    # ----------MAIN----------
    n, k = get_li()
    print(n - k + 1)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()


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

int CountIsland(int w,int h,int c[][50]);
void CheckIsland(int w,int h,int c[][50]);
void debugg(int w,int h,int c[][50]);
int main(){
	int w,h;
	int c[50][50];
	while(true){
		for(int i=0;i<50;i++){
			for(int j=0;j<50;j++){
				c[i][j]=-1;
			}
		}
		cin >> w >> h;
		if(w==0&&h==0){break;}
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				cin >> c[i][j];
			}
		}
		cout << CountIsland(w,h,c) << endl;
	}
	return 0;
}
int CountIsland(int w,int h,int c[][50]){
	int r=0;
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			if(c[i][j]==1){
				r++;
				CheckIsland(j,i,c);
			}
		}
	}
	return r;
}
void debugg(int w,int h,int c[][50]){
	cout << endl;
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			cout << c[i][j] << " ";
		}
		cout << endl;
	}
}
void CheckIsland(int w,int h,int c[][50]){
	c[h][w] = 0;
	for(int i=-1;i<=1;i++){
		for(int j=-1;j<=1;j++){
			if(i == -1 && h == 0 || j == -1 && w == 0 || i == 1 && h == 49 || j == 1 && w == 49||i == 0 && j == 0){continue;}
			if(c[i+h][j+w]==1){
				CheckIsland(j+w,i+h,c);
			}
		}
	}
}

Measured memory_bytes: 1388
#include<bits/stdc++.h>
using namespace std;
#define res register int
#define ll long long
//#define cccgift
//#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
//char buf[1<<21],*p1=buf,*p2=buf;
template<typename T>
inline void read(T &x)
{
    static char ch;bool f=1;
    for(x=0,ch=getchar();!isdigit(ch);ch=getchar()) if(ch=='-') f=0;
    for(;isdigit(ch);x=(x<<1)+(x<<3)+(ch^48),ch=getchar());x=f?x:-x;
}
template<typename T>
void print(T x)
{
    if (x<0) x=-x,putchar('-');
    if (x>9) print(x/10);
    putchar(x%10+48);
}
template<typename T>
inline void print(T x,char ap) {print(x);if (ap) putchar(ap);}
template<typename T>
inline void chkmax(T &x,const T &y) {x=x<y?y:x;}
template<typename T>
inline void chkmin(T &x,const T &y) {x=x<y?x:y;}
int n,ver[200001],nxt[200001],edge[200001],head[100001],ans,du[100001],x,y,k,col[100001];
void dfs(int x,int fa,int nowcol) {
	int totcol=0;
	for(res i=head[x];i;i=nxt[i]) {
		if(ver[i]==fa) continue;
		++totcol;if(totcol==nowcol) ++totcol;
		col[edge[i]]=totcol,dfs(ver[i],x,totcol);
	}
}
inline void add(int x,int y,int z) {ver[++ans]=y,edge[ans]=z,nxt[ans]=head[x],head[x]=ans;}
int main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	for(res i=1;i<n;++i) cin>>x>>y,add(x,y,i),add(y,x,i),++du[x],++du[y];
	for(res i=1;i<=n;++i) chkmax(k,du[i]);
	dfs(1,0,0);
	cout<<k<<'\n';
	for(res i=1;i<n;++i) cout<<col[i]<<'\n';
	cout<<flush;
	return 0;
}
/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?), set tle
    * do something instead of nothing and stay organized
*/ 

Measured memory_bytes: 5248
import java.util.*;
public class Main{
    public static void main(String[] args){
	Scanner in = new Scanner(System.in);
	double a,b,c;
	double C,S,L,h;

	a = in.nextDouble();
	b = in.nextDouble();
	C = in.nextDouble();

	h = b*Math.sin(C/180*Math.PI);
	S = a*h/2;
	c=Math.sqrt(Math.pow(a,2)+Math.pow(b,2)-2*a*b*Math.cos(C/180*Math.PI));
	
	System.out.printf("%.8f\n%.8f\n%.8f\n",S,a+b+c,h);
    }
}



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

int main() {
	int a, b;
	cin >> a >> b;
	int ans = 0;
	for (int i = 0; i < 2; i++) {
		if (a >= b) {
			ans += a;
			a--;
		}
		else {
			ans += b;
			b--;
		}

	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
  int a,b,c;
  cin>>a>>b>>c;
  int k;
  cin>>k;
  
      
      while(b<=a && k>0){
          b = b*2;
          
          k--;
        //   cout<<b<<" "<<k<<endl;
      }
      while(c<=b && k>0){
          c = c*2;
          k--;
        // cout<<c<<" "<<k<<endl;

      
  }
//   cout<<a<<" "<<b<<" "<<c<<endl;
  if(c>b && b>a){
      cout<<"Yes"<<endl;
  }else{
      cout<<"No"<<endl;
  }


  
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(0), cin.tie(0) 
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int inf = ~0u >> 1;
int main() {
    IO;
    ll x;
    cin >> x;
    ll sum = 100;
    int ans = 0;
    while (sum < x) {
        sum += ll(0.01 * sum);
        ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A,B,C,K;
  int sum=0;
  cin >> A >> B >> C >> K;
  
  if (A>K)
  	cout << K << endl;
  else if (A+B > K)
    cout << A << endl;
  else
    cout << 2*A+B-K << endl;
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using ll = long long;
using Graph = vector<vector<int>>;

int main()
{
    int N;
    cin >> N;
    bool ans = false;
    rep(i, 9)
    {
        rep(j, 9)
        {
            if (N == (i + 1) * (j + 1))
            {
                ans = true;
                break;
            }
        }
    }
    if (ans)
    {
        cout << "Yes" << endl;
    } else
    {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
N, *L,  = [list(map(int, s.split())) for s in open(0)]
A = L[0]

cnt = 0
for i in range(len(A) - 2):
    ma = max(A[i], A[i+1], A[i+2])
    mi = min(A[i], A[i+1], A[i+2])
    if A[i+1] not in [ma, mi]:
        cnt += 1
print(cnt)

Measured memory_bytes: 3064
#include <stdio.h>

int main (void){


double r,menseki=0,enshu=0,M_PI=3.14159265359;


scanf("%lf",&r);


menseki=r*r*M_PI;


enshu=r*2.0*M_PI;


printf("%f %f\n",menseki,enshu);


return 0;


}

Measured memory_bytes: 648
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    bool flag = false;
    for(int i = 1; i < 10 ; i ++ ){
        if(n % i == 0 && n / i <= 9){
            printf("Yes");
            flag = true;
            break;
        }
    }
    if(!flag) printf("No");
    return 0;
}

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

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

int main()
{
  int n;
  cin >> n;
  for (int t = 1; t <= n; ++t) {
    int x, y;
    vector<string> field(8);
    for (int i = 0; i < 8; ++i)
      cin >> field[i];
    cin >> x >> y;
    --x;
    --y;

    queue<pair<int, int> > que;
    que.push(pair<int, int>(x, y));
    while (!que.empty()) {
      const pair<int, int> p = que.front();
      que.pop();
      field[p.second][p.first] = '0';

      for (int d = 0; d < 4; ++d) {
	for (int k = 0; k < 3; ++k) {
	  pair<int, int> pp(pair<int, int>(p.first+dx[d][k], p.second+dy[d][k]));
	  if (pp.first < 0 || 8 <= pp.first ||
	      pp.second < 0 || 8 <= pp.second|| 
	      field[pp.second][pp.first] == '0')
	    continue;
	  que.push(pp);
	}
      }
    }

    cout << "Data " << t << ":" << endl;
    for (int i = 0; i < 8; ++i)
      cout << field[i] << endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define INF 9223372036854775807LL
#define inf 1000000007
#define SYOU(x) setprecision(x+1)
#define abs(x,y) (max(x,y)-min(x,y))
#define lol long long
#define mp make_pair
#define fi first
#define se second
using namespace std;
lol a,b,c,d;
int i[100000];
int u[100000];
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s,w;
  cin >>a>>b;
  if(a*500>=b) cout <<"Yes\n";
  else cout <<"No\n";
  return (0);
}


Measured memory_bytes: 256
S = str(input())
if S[0] == S[1] == S[2] == S[3]:
    print('No')
elif S[0] == S[1] and S[2] == S[3]:
    print('Yes')
elif S[0] == S[2] and S[1] == S[3]:
    print('Yes')
elif S[0] == S[3] and S[1] == S[2]:
    print('Yes')
else:
    print('No')

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

using namespace std;

void Run() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (int& x : a) cin >> x;
  int lo = 1;
  int hi = 1e9;
  auto Can = [&](int mid) {
    long long tot = 0;
    for (int i = 0; i < n; ++i)
      tot += (a[i] + mid - 1) / mid - 1;
    return tot <= k;
  };
  while (lo < hi) {
    int mid = (lo + hi) / 2;
    if (Can(mid)) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
  }
  cout << hi << '\n';
}

int main() {
  srand(time(0));
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); 
  Run();
  return 0;
}

Measured memory_bytes: 3944
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
//    freopen("in.txt", "r", stdin);
    int a, b, c, x;
    scanf("%d%d%d%d", &a, &b, &c, &x);
    x /= 50;
    int ans = 0;
    for (int i = 0; i <= min(a, x/10); ++i) {
        for (int j = 0; j <= min(b, (x-i*10)/2); ++j) {
            if (x - i * 10 - j * 2 <= c) ++ans;
        }
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<numeric>
#include<map>
#include<iostream>
#include<iomanip>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;
typedef pair<ll, ll> mp;


/*
AC
dp1 = lからrまでのスライムを合体させる最小コスト
dp2 = 累積和（合体後のスライムの重さを高速に計算するため）
*/


ll n,a[410],dp[410][410],dp2[410],ans=0;

ll f(ll l,ll r){
	if(l==r)return 0;
	if(dp[l][r]!=0)return dp[l][r];
	ll smallest=1e18;
	reg(i,l,r-1){
		smallest = min(smallest, f(l,i)+f(i+1,r));
	}
	return dp[l][r]=smallest+dp2[r]-dp2[l-1];
}

int main(void){
	cin>>n;
	reg(i,1,n)cin>>a[i];
	//
	dp2[0]=0;
	reg(i,1,n)dp2[i]=dp2[i-1]+a[i];
	reg(i,1,n)rep(j,n)dp[i][j]=0;
	//
	cout<<f(1,n)<<endl;
	return 0;
}

Measured memory_bytes: 1536
package main

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

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	a := scanInt(sc)
	b := scanInt(sc)
	k := scanInt(sc)

	for i := 0; i < k/2; i++ {
		process(&a, &b)
		process(&b, &a)
	}

	if k%2 == 1 {
		process(&a, &b)
	}

	fmt.Println(a, b)
}

func process(x, y *int) {
	if *x%2 == 1 {
		*x -= 1
	}
	*y += *x / 2
	*x = *x / 2
}

func scanInt(sc *bufio.Scanner) int {
	sc.Scan()
	v, _ := strconv.Atoi(sc.Text())
	return v
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define rep(i,n) for(int i=0;i<n;i++)
const long long MOD = 1000000007;
const long long INF = MOD*MOD;
typedef pair<int,int> P;
typedef long long ll;
ll n,m,k,ans;
string s;

int main(){
  int n,a,b;cin >> n >> a >> b;
  if((a-b)%2){
    cout << "Borys\n";
  }else{
    cout << "Alice\n";
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define pll  pair <long long,long long>
#define ss second
#define ff first
#define inf 9223372036854775807
#define maa 998244353
#define ld long double
#define fast  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define bug(x) cout << #x <<": " << x << '\n';
const ll N=200001 ;
int main()
{
   fast ;
   ll n,d ;
   cin>>n>>d ;
   ll a=0 ;
   for(ll i=0;i<d;i++)
   {
       ll x ;
       cin>>x ;
       a+=x ;
   }
   if(a>n)
    cout<<"-1" ;
   else
   {
       cout<<(n-a) ;
   }





}


Measured memory_bytes: 3640
#include <iostream>

using namespace std;


int main(){
    string s;
    cin >> s;
    int ans = 10000;
    for(int i = 0; i < 26; i++){
        char c = 'a'+i;
        int tmp = 0;
        int m = 0;
        for(int j = 0; j < s.size(); j++){
            if(s[j] == c){
                m = max(m, tmp);
                tmp = 0;
            }else{
                tmp++;
            }
            if(j+1 == s.size()) m = max(m, tmp);
        }
        ans = min(m, ans);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ALL(c) begin(c), end(c)
using namespace std;
using ll = long long;
using ld = long double;



int main(){
	//freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);//cout.precision(12);cout<<fixed;
	
	int n;
	
	cin>>n;
	vector<int> a(n);
	for(auto &_ : a) cin>>_;
	
	vector<int> b(n);
	for(auto &_ : b) cin>>_;
	
	vector<int> ans(n);
	vector<int> p;
	vector<int> f;
	for(int i=0;i<n;++i) if(a[i]==b[i]) p.push_back(i);
	else ans[i] = b[i], f.push_back(i);
	
	int m = size(p);
	vector<int> cnt(n+1);
	for(int i : p) ++cnt[b[i]];
	
	int r = max_element(ALL(cnt)) - begin(cnt);
	
	vector<int> pr;
	for(int i : p) if(b[i]==r) pr.push_back(i);
	
	vector<int> del;
	for(auto i : f){
		if(cnt[r]*2<=m) break;
		if(a[i]!=r && b[i]!=r){
			ans[i] = r;
			ans[pr.back()] = b[i];
			del.push_back(pr.back());
			pr.pop_back();
			--cnt[r];
			--m;
		}
	}
	
	set<int> u(ALL(p));
	for(int i : del) u.erase(i);
	assert(size(u) == m);
	
	p.assign(ALL(u));
	
	if(cnt[r]*2>m){
		cout<<"No"<<endl;
		return 0;
	}
	
	for(int k=0;k<m;++k){
		int i = p[k], j = p[(k+cnt[r])%m];
		assert(ans[j]==0);
		ans[j] = b[i];
	}
	
	cout<<"Yes"<<endl;
	for(int x : ans) cout<<x<<' ';
	cout<<endl;
	
	
	
	for(int i=0;i<n;++i) assert(ans[i]!=a[i]);
	
	
	return 0;
}


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------


class SCC {
public:
	static const int MV = 2025000;
	vector<vector<int> > SC; int NV,GR[MV];
private:
	vector<int> E[MV], RE[MV], NUM; int vis[MV];
public:
	void init(int NV) { this->NV=NV; for(int i=0;i<NV;i++) { E[i].clear(); RE[i].clear();}}
	void add_edge(int x,int y) { E[x].push_back(y); RE[y].push_back(x); }
	void dfs(int cu) { vis[cu]=1; for(int i=0;i<E[cu].size();i++) if(!vis[E[cu][i]]) dfs(E[cu][i]); NUM.push_back(cu); }
	void revdfs(int cu, int ind) { int i; vis[cu]=1; GR[cu]=ind; SC[ind].push_back(cu);
		FOR(i,RE[cu].size()) if(!vis[RE[cu][i]]) revdfs(RE[cu][i],ind);}
	void scc() {
		int c=0,i; SC.clear(); SC.resize(NV); NUM.clear();
		assert(NV);
		FOR(i,NV) vis[i]=0; FOR(i,NV) if(!vis[i]) dfs(i); FOR(i,NV) vis[i]=0;
		for(int i=NUM.size()-1;i>=0;i--) if(!vis[NUM[i]]){
			SC[c].clear(); revdfs(NUM[i],c); sort(SC[c].begin(),SC[c].end()); c++;
		}
		SC.resize(c);
	}
};

SCC scc;
int N,M;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	scc.init(N);
	FOR(i,M) {
		cin>>x>>y;
		scc.add_edge(x,y);
	}
	scc.scc();
	cout<<scc.SC.size()<<endl;
	FORR(v,scc.SC) {
		cout<<v.size();
		FORR(w,v) cout<<" "<<w;
		cout<<endl;
	}

}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


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

int main() {
    int n,m; cin >>n;
    m = n/1.08;

    for(int i=m-10; i<m+10; i++){
      int l; l=1.08*i;
     
      
        if(l==n){
            cout << i << endl;
            return 0;
        }else{
            continue;
        }
    }cout << ":("<< endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <array>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#define _USE_MATH_DEFINES
#include <cmath>
#include <climits>
#include <cstdio>
#include <iomanip>
#include <utility>
#include <unordered_map>

using namespace std;
typedef long long int ll;

#define SP(x) setprecision((int)x)
#define SW(x) setw(x)    // 桁数指定
#define SF(c) setfill(c) // 埋め文字指定('0')
#define ALL(v) v.begin(), v.end()

ll gcd(ll x, ll y)
{
    while (y > 0)
    {
        ll tmp = y;
        y = x % y;
        x = tmp;
    }
    return x;
}

ll lcm(ll x, ll y)
{
    return x / gcd(x, y) * y;
}

// 素因数分解O(sqrt(n))
map<ll, ll> prime_factor(ll n) {
    map<ll, ll> res;
    for (ll i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            ++res[i];
            n /= i;
        }
    }
    if (n != 1) res[n] = 1;
    return res;
}

int main(int argc, char const *argv[])
{
    ll n;
    cin >> n;

    vector<ll> a(n);

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

    bool ispairwise = true;
    map<ll, ll> m;
    for (ll i = 0; i < n; i++)
    {
        auto p = prime_factor(a[i]);
        for (auto t : p)
        {
            if (m[t.first] > 0)
            {
                ispairwise = false;
                break;
            }
            else{
                m[t.first] = t.second;
            }
        }
        if (!ispairwise)
        {
            break;
        }
    }

    bool issetwise = false;

    ll t = a[0];
    for (ll i = 1; i < n; i++)
    {
        t = gcd(t, a[i]);
        if (t == 1)
        {
            issetwise = true;
            break;
        }
    }

    if (ispairwise)
    {
        cout << "pairwise coprime" << endl;
    }
    else if (issetwise)
    {
        cout << "setwise coprime" << endl;
    }
    else
    {
        cout << "not coprime" << endl;
    }
}

Measured memory_bytes: 11176
#include <cstdio>
#include <cmath>
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <queue>
using namespace std;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define REP(i,n) for(ll i=0;i<n;i++)
#define REPR(i,n) for(ll i=n-1;i>=0;i--)

typedef long long ll;
#define INF 1e18

int main(){
	ll a; cin>>a;
	ll b; cin>>b;
	ll k; cin>>k;
	if(a>=k){
		cout<<a-k<<" "<<b<<endl;
	}else if(a+b>=k){
		cout<<0<<" "<<a+b-k<<endl;
	}else{
		cout<<0<<" "<<0<<endl;
	}
	return 0;
}


Measured memory_bytes: 256
a = int(input())
S = 'abcdefghij'

def dfs(s,c):
    if c == a:
        ans.append(s)
        return 
    for i in S[:c+1]:
        if i in s:dfs(s+i,c+1)
        else:
            dfs(s+i,c+1)
            return 
ans = []

dfs("",0)

for i in ans:
    print(i)

Measured memory_bytes: 12664
# 2019/09/06

input=open(0).readline
q=int(input())

lr=[]
mxr=0

for i in range(q):
    l,r=map(int,input().split())
    lr.append((l,r))
    mxr=max(mxr,r)

def sieve(n):
    end=int(pow(n,0.5))+1
    is_prime=[True]*(n+1)
    is_prime[0]=False
    is_prime[1]=False

    for i in range(2,end+1):
        if not is_prime[i]:continue
        for j in range(i*2,n+1,i):
            is_prime[j]=False
    return is_prime

prime=sieve(mxr)

x=[0]
cnt=0
for i in range(1,mxr+1):
    if prime[i]&prime[(i+1)//2]:
        cnt+=1
    x.append(cnt)
for l,r in lr:
    print(x[r]-x[l-1])

Measured memory_bytes: 18904
// 問題名: Edit Distance
// URL: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C&lang=jp
// 所要時間: 40分(カンニングあり)
// --感想--
// 編集距離が出てくる問題は何度か解いたことがあったが、編集距離そのものを求める問題を解いたことがなかったため、
// 典型問題に触れることができて良い勉強になった。考察は考えても浮かばなかったため、
// https://qiita.com/odenmonster/items/db443d5808788a869fe9
// こちらのサイトを参考にした。

#include <bits/stdc++.h>
using namespace std;

int n;
void dfs(int level, pair<double, double> pl, pair<double, double> pr){
    if(level < n){
        pair<double, double> p1, p2, p3; // 新しくできる頂点
        p1 = make_pair((pl.first * 2 + pr.first) / 3, (pl.second * 2 + pr.second) / 3);
        p3 = make_pair((pl.first + pr.first * 2) / 3, (pl.second + pr.second * 2) / 3);
        pair<double, double> v = make_pair(p3.first-p1.first, p3.second-p1.second); // p3-p1
        double a = v.first, b = v.second, r3 = sqrt(3);
        v = make_pair(a / 2 - b * r3 / 2, a * r3 / 2 + b / 2); // vを反時計回りに60度回転
        p2 = make_pair(p1.first + v.first, p1.second + v.second);
        dfs(level + 1, pl, p1);
        dfs(level + 1, p1, p2);
        dfs(level + 1, p2, p3);
        dfs(level + 1, p3, pr);
    }
    else
        cout << pl.first << " " << pl.second << endl;
    if(level == 0)
        cout << pr.first << " " << pr.second << endl;
}

int main(){
    cin >> n;
    dfs(0, make_pair(0.0, 0.0), make_pair(100.0, 0.0));
}


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

int main() {
    string S; cin >> S;
    long long ans = 0, num = 0;
    for (long long i = 0; i < 3; i++) {
        if (S.at(i) == 'R') num++;
        else {
            ans = max(ans, num);
            num = 0;
        }
    }
    cout << max(ans, num) << endl;
}

Measured memory_bytes: 3624
/**
 *     author: qodjf
 *     created: 06.03.2020 19:48:49
 */
#include <bits/stdc++.h>
using namespace std;

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

#define all(a) begin(a), end(a)
#define rep(i, begin, end)                            \
  for (__typeof(end) i = (begin) - ((begin) > (end)); \
       i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))

using ll = long long;

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

  int N, x;
  cin >> N >> x;
  vector<int> a(N), b(N, INT_MAX);
  rep(i, 0, N) { cin >> a[i]; }
  ll ans = LONG_LONG_MAX;
  rep(k, 0, N) {
    ll sum = 1ll * k * x;
    rep(i, 0, N) {
      chmin(b[i], a[(i - k + N) % N]);
      sum += b[i];
    }
    chmin(ans, sum);
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <iostream>
#include <iomanip>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <bitset>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;
typedef pair<int, int> Pii;

const ll MOD = 1000000007;
const long double EPS = 1e-10;
const int dyx[4][2] = {
    { 0, 1}, {-1, 0}, {0,-1}, {1, 0}
};

int main() {
    std::ios::sync_with_stdio(0); cin.tie(0);
    int a,b,c,d,e,f;
    cin >> a >> b >> c >> d >> e >> f;

    int ans_water = 0, ans_sugar = 0;
    for(int ia=0;ia<=f/(100*a);++ia) {
        for(int ib=0;ib<=(f-100*a*ia)/b;++ib) {
            for(int ic=0;ic<=(f-100*a*ia-100*b*ib)/c;++ic) {
                for(int id=0;id<=(f-100*a*ia-100*b*ib-c*ic)/d;++id) {
                    int water = 100 * (a * ia + b * ib);
                    int sugar = c * ic + d * id;
                    if(100 * sugar > water * e || water+sugar > f) continue;
                    if(sugar * (ans_water+ans_sugar) >= ans_sugar * (sugar+water)) {
                        ans_water = water;
                        ans_sugar = sugar;
                    }
                }
            }
        }
    }

    cout << ans_water+ans_sugar << " " << ans_sugar << endl;
}


Measured memory_bytes: 256
#ifdef LOCAL111
	#define _GLIBCXX_DEBUG
#else
	#define NDEBUG
#endif
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
const int INF = 1e8;
using namespace std;
template<typename T, typename U> ostream& operator<< (ostream& os, const pair<T,U>& p) { cout << '(' << p.first << ' ' << p.second << ')'; return os; }

#define endl '\n'
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#ifdef LOCAL111
	#define DEBUG(x) cout<<#x<<": "<<(x)<<endl
	template<typename T> void dpite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
#else
	#define DEBUG(x) true
	template<typename T> void dpite(T a, T b){ return; }
#endif
#define F first
#define S second
#define SNP string::npos
#define WRC(hoge) cout << "Case #" << (hoge)+1 << ": "
template<typename T> void pite(T a, T b){ for(T ite = a; ite != b; ite++) cout << (ite == a ? "" : " ") << *ite; cout << endl;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}

typedef long long int LL;
typedef unsigned long long ULL;
typedef pair<int,int> P;

void ios_init(){
	//cout.setf(ios::fixed);
	//cout.precision(12);
#ifdef LOCAL111
	return;
#endif
	ios::sync_with_stdio(false); cin.tie(0);	
}

int main()
{
	ios_init();
	string s;
	while(cin >> s) {
		int n = s.size();
		map<int,int> dp;
		dp[0] = 0;
		using bs = bitset<26>;
		bs tmp = 0;
		int ans;
		REP(i,n){
			int c = s[i]-'a';
			tmp[c] = !tmp[c];
			int mi = INF;
			REP(j,26){
				auto t = tmp;
				t[j] = !t[j];
				auto ite = dp.find(t.to_ulong());
				if(ite != dp.end()) {
					chmin(mi, ite->S+1);
				}
			}
			{
				auto ite = dp.find(tmp.to_ulong());
				if(dp.find(tmp.to_ulong()) != dp.end()){
					chmin(mi,ite->S+1);
				}
			}
			ans = mi;

			{
				auto ite = dp.find(tmp.to_ulong());
				if(ite == dp.end()) {
					dp[tmp.to_ulong()] = INF;
				}
			}
			chmin(dp[tmp.to_ulong()], mi);
		}
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 9876
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)


int main() {
    int a, b, c, x, y;
    cin >> a >> b >> c >> x >> y;

    int ans=1e7;
    int min=a*x+b*y;
    for(int i=0; i <= max(x,y); i++){
        ll apizza = max(0, x-i);
        ll bpizza = max(0, y-i);
        ans = i*2*c+apizza*a+bpizza*b;
        if(min > ans) min = ans;
    }
    cout <<  min << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	
	public static void main(String[] args)  {
		Scanner scan = new Scanner(System.in);
		int n=Integer.parseInt(scan.next());
		long sum=0;
		for (int i=0;i<=n;++i) {
			if (i%3!=0&&i%5!=0)sum+=i;
		}
		System.out.print(sum);
	
}
}
//end

Measured memory_bytes: 35688
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define pf push_front
#define mod 1000000007
#define endl '\n'
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

int main()
{
   string s;
   cin>>s;
   ll j;
   vector<string>v;
   for(char a='1';a<='9';a++)
   {
       string str="";
       for(j=0;j<s.length();j++)
       {
           str+=a;
       }
       v.pb(str);
   }
   //cout<<v[0]<<endl;
   for(ll i=0;i<v.size();i++)
   {
       if(v[i]>=s)
       {
           return(cout<<v[i]<<endl, 0);
       }
   }

}


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

using namespace std;

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

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

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

#define MP make_pair
#define EACH(i,c) for(auto i: c)
#define SORT(c) sort((c).begin(),(c).end())

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

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int N;
	cin >> N;
	map<int, int> m[2];
	REP(_, N){
		int v;
		cin >> v;
		m[_ & 0x01][v]++;
	}

	vector<PII> v[2];
	EACH(a, m[0]) v[0].push_back(MP(a.second, a.first));
	EACH(a, m[1]) v[1].push_back(MP(a.second, a.first));

	v[0].push_back(MP(-1e9, -1));
	v[1].push_back(MP(-1e9, -1));

	SORT(v[0]);
	SORT(v[1]);

	int ret = 1e9;
	REP(i, 2){
		REP(j, 2){
			int ii = v[0].size() - i - 1;
			int jj = v[1].size() - j - 1;
			if(v[0][ii].second != v[1][jj].second) ret = min(ret, N - v[0][ii].first - v[1][jj].first);
		}
	}
	if(ret == 1e9) ret = N / 2;

	cout << ret <<endl;
	return 0;
}


Measured memory_bytes: 6140
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
l=[[0,0] for _ in range(m)]
for i in range(m):
    l[i][1],l[i][0]=map(int,input().split())

l=sorted(l)

ans=1

c=l[0][0]
for i in range(m):
    if l[i][1]>=c:
        ans+=1
        c=l[i][0]
    else:
        continue
print(ans)


Measured memory_bytes: 20784
#include<bits/stdc++.h>
#define ll long long int
#define pii pair<int,int>
#define F first
#define S second
#define mod 998244353
using namespace std;

int main(){
    int n,m;cin >>n>>m;
    int ans=0;
    if(n>1){
        ans+=(n*(n-1))/2;
    }
    if(m>1){
        ans+=(m*(m-1))/2;
    }
    cout <<ans<<endl;

}


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

using pii = pair<int,int>;
using ll = long long;
using ull = unsigned long long;
#define rep(i, j) for(int i=0; i < (int)(j); i++)
#define repeat(i, j, k) for(int i = (j); i < (int)(k); i++)
#define all(v) v.begin(),v.end()
#define debug(x) cerr << #x << " : " << x << endl

template<class T> bool set_min(T &a, const T &b) { return a > b  ? a = b, true : false; }
template<class T> bool set_max(T &a, const T &b) { return a < b  ? a = b, true : false; }
// vector
template<class T> istream& operator >> (istream &is , vector<T> &v) { for(T &a : v) is >> a; return is; }
template<class T> ostream& operator << (ostream &os , const vector<T> &v) { for(const T &t : v) os << "\t" << t; return os << endl; }
// pair
template<class T, class U> ostream& operator << (ostream &os , const pair<T, U> &v) { return os << "<" << v.first << ", " << v.second << ">"; }

const int INF = 1 << 30;
const ll INFL = 1LL << 60;
/*
  s := s1 s2 ... sn

  hash[1_to_i] := s1*b^(i-1) + s2*b^(i-2) + ... + si*b^0

  hash[1_to_j] := s1*b^(j-1) + s2*b^(j-2) + ... + si*b^(j-i) + ... + sj*b^0


  hash[(i+1)_to_j] = hash[1_to_j] - hash[1_to_i]*b^(j-i)

                   = s(i+1)*b^(j-i-1) + ... + sj*b^0
*/

typedef unsigned long long ull;
const ull HASH_BASE = 100000007;
// build O(N), query O(1)
// MOD は over-flow で代用している
array<ull, 1000> pow_base;
function<ull(int, int)> build_rolling_hash(const string &s) {
    int n = s.size();
    vector<ull> hash(n + 1);
    pow_base[0] = 1;
    rep(i, n) {
        hash[i + 1] = hash[i] * HASH_BASE + s[i];
        pow_base[i + 1] = pow_base[i] * HASH_BASE;
    }
    return [=] (int l, int r) {
        return hash[r] - hash[l] * pow_base[r - l];
    };
}

class Solver {
  public:
    bool solve() {
        int N; cin >> N;
        vector<string> S(N); cin >> S;
        vector<function<ull(int, int)>> hash_r(3 * N), hash_c(3 * N);

        rep(i, 3 * N) {
            {
                int r = i;
                string s;
                s.reserve(3 * N);
                rep(j, 3 * N) s.push_back(S[(r + j) % N][j % N]);
                hash_r[i] = build_rolling_hash(s);
            }
            {
                int c = i;
                string s;
                s.reserve(3 * N);
                rep(j, 3 * N) s.push_back(S[j % N][(c + j) % N]);
                hash_c[i] = build_rolling_hash(s);
            }
        }
        ll ans = 0;
        rep(r, N) {
            rep(c, N) {
                bool ok = true;
                rep(i, N) {
                    ok &= hash_r[r - c + N + i](c, c + N) == hash_c[c - r + N + i](r, r + N);
                }
                ans += ok;
            }
        }
        cout << ans << endl;
        return 0;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    Solver s;
    s.solve();
    return 0;
}


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

string ans = "";
string s,t,tmp = "";
int ls,lt,flag;

int main() {
	cin >> s >> t;
	ls = s.size();lt = t.size();
	if(ls < lt)  {
		puts("UNRESTORABLE");
		return 0;
	}
	for(int i = 0;i < ls - lt + 1;i++) {
		tmp = s;flag = 0;
		for(int j = i;j < i + lt;j++) {
			if(tmp[j] == '?') tmp[j] = t[j - i];
			else {
				if(tmp[j] != t[j - i]) {
					flag = 1;
					break;
				}
			}
		}
	//	cout << tmp << "\n";
		if(flag == 0) {
			for(int j = 0;j < ls;j++) {
				if(tmp[j] == '?') tmp[j] = 'a';
			}
			if(ans == "") ans = tmp;
			else ans = min(ans,tmp);
		}
	}
	if(ans != "") cout << ans << "\n";
	else puts("UNRESTORABLE");
	return 0;
}

Measured memory_bytes: 3604
/*
Created on Thu Aug 27 21:32:39 2020

@author: roastedcoder

*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long int ull;
const int mod = 1e9+7;
const int INF = INT_MAX;
#define endl "\n"
#define append push_back
#define roastedcoder ios_base::sync_with_stdio(false); cin.tie(NULL);
//__________________________________________________________________


int main() {
	roastedcoder
	ll n; cin>>n;
	ll a[n], dp[n] = {0};
	cin>>a[0];
	dp[0] = a[0];
	for(int i = 1; i<n; i++) {
		cin>>a[i];
		dp[i] = dp[i-1]+a[i];
	}
	ll res = 0;
	for(int i = 0; i<n; i++) {
		res += (((dp[n-1] - dp[i])%mod)*a[i])%mod;
	}
	cout<<res%mod<<endl;
}

//__________________________________________________________________
/*
Sample Input:


Sample Output:


*/


Measured memory_bytes: 6776
#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for(ll i = 0;i < n;i++)
#define ll long long
#define MOD 1000000007
using vi = vector<int>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける

int n,m;


class SegTree
{
  public:
  ll n2;//2のべき乗になる数でn以上の数
  ll ln2;//n2のlog2値
  vector<pair<ll,ll>> data;//●●●●●●●●●●●●●●●●●●●●●●●●●●●●●


  SegTree(ll ninput)
  {
    ll il=0LL;
    for(ll i=1LL;i<(1LL<<62LL);i*=2)
    {
      if (i>=ninput)
      {
        n2=i;
        ln2=il;
        break;
      }
      il++;
    }

    data.resize(n2*2);
    /*
    for(int i=0;i<n2*2;i++){
      data[i]=Initval();//●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
    }
    */
  }


  //min関数的な
  //●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
  pair<ll,ll> SGTfunc(pair<ll,ll> d0,pair<ll,ll> d1){
    if (d0.first>=d1.first){
      return d0;
    }else{
      return d1;
    }
  }

  //データをセットして内部更新 O(logn)
  void Updata(int posi,pair<ll,ll> d)
  {
    int myi=posi+n2;
    data[myi]=d;//葉
    for(int i=0;i<ln2;i++){//中間要素
      myi/=2;
      data[myi]=SGTfunc(data[myi*2],data[myi*2+1]);
    }
  }

  //lを含むrを含まないところまでの区間
  pair<ll,ll> GetMin(int l,int r)
  {
    pair<ll,ll> ret=data[l];//●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
    int l_=l;
    int r_=r;
    for(int i=0;(l_+r_)>0;i++){
      int offset=1<<(ln2-i);
      if (r_%2==1){
          if (r_-1>=l_){
            ret=SGTfunc(ret,data[offset+r_-1]);
            r_--;
          }
      }
      if (l_%2==1){
          if (l_<r_){
            ret=SGTfunc(ret,data[offset+l_]);
            l_++;
          }
      }
      r_>>=1;
      l_>>=1;
    }
    return ret;
  }

};






int main(){
  ll ans=0LL;
  cin >> n >>m;
  vector<pair<ll,ll>> ab(n);

  REP(i,n){
    cin>>ab[i].first>>ab[i].second;
  }

  sort(ab.begin(), ab.end());


  SegTree segtree(n);
  //////////////////////////////////////////////////////////////////////////////////////////////////////////////
  REP(i,segtree.n2){
      pair<ll,ll> tmp;
      tmp.first=0LL;
      tmp.second=i;
      segtree.Updata(i,tmp);
  }
  //////////////////////////////////////////////////////////////////////////////////////////////////////////////
  int segw=0;
  int bread=0;

  //最後の1日に受けられる仕事
  //最後の2日に受けられる仕事・・・Mループ
  for(int i=1;i<m+1;i++){
    for(;bread<n;bread++){
      if (ab[bread].first==i){
        pair<ll,ll> p;
        p.first=ab[bread].second;
        p.second=segw;
        segtree.Updata(segw,p);
        segw++;
      }else{
        break;
      }
    }

    if (segw!=0){
      pair<ll,ll> tmp;
      tmp=segtree.GetMin(0,segw);
      ans+=tmp.first;
      pair<ll,ll> p;
      p.first=0LL;
      p.second=tmp.second;
      segtree.Updata(tmp.second,p);
    }
  }

  cout<<ans<<endl;


  return 0;
}

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

int main() {
  int N;
  cin >> N;
  vector<int> input(N);

  for(int i = 0 ; i < N ; i++){
  	cin >> input.at(i); 
  }

  int count = 0;
  bool flag = true;
  
  while(true){
  	for(int i = 0;i <N ; i++){
   		if(input.at(i)%2 == 0){
     		input.at(i) = input.at(i)/2; 
    	}
		else{
      		flag = false;
      		break;
    	}
    }
   	if(flag == true){
    	count += 1;
//       cout << "count" << endl;
    }
   	else{
    	break;
    }
//    cout << count << endl;
  }
  cout << count << endl;
}




Measured memory_bytes: 256
from collections import deque

n = int(input())
g = [[] for i in range(n)]
for i in range(n-1):
    a,b,c = map(int,input().split()); a-=1;b-=1
    g[a].append([b, c]); g[b].append([a, c])

fromzero = [0]*n

res = [0]*n
q = deque([0])
visited = [0]*n; visited[0] = 1
while q :
    now = q.popleft()
    for nxt, c in g[now] :
        if visited[nxt] : continue
        visited[nxt] = 1
        fromzero[nxt] = fromzero[now] + c
        d = fromzero[nxt]
        res[nxt] = (d % 2)
        q.append(nxt)

print(*res, sep='\n')


Measured memory_bytes: 52500