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

typedef int Weight;
struct Edge {  
  int src, dst;
  Weight weight;
  Edge(int src, int dst, Weight weight) :
    src(src), dst(dst), weight(weight) { }
};
bool operator < (const Edge &e, const Edge &f) {
  return e.weight != f.weight ? e.weight > f.weight : 
    e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

const long long INF=2*1e9;
bool shortestPath(const Graph &g,vector<vector<Weight>> &dist,vector<vector<int>> &inter) {
  int n = g.size();
  dist.assign(n,vector<Weight>(n,INF));
  for(int i=0;i<n;i++) dist[i][i]=0;
  for(int i=0;i<n;i++){
    for(auto f : g[i]) dist[i][f.dst]=f.weight;
  }
  inter.assign(n, vector<int>(n,-1));
  for(int k=0;k<n;k++){
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
        if(dist[i][k]<INF && dist[k][j]<INF && dist[i][j]>dist[i][k]+dist[k][j]){
          dist[i][j] = dist[i][k] + dist[k][j];
          inter[i][j] = k;
        }
      }
    }
  }
  for(int i=0;i<n;i++){
    if(dist[i][i]<0) return false;
  }
  return true;
}

int main(){
	int v, e; cin >> v >> e;
	Graph g(v);
    int s, t, w;
    for(int i=0; i<e; i++){
        cin >> s >> t >> w;
        g[s].push_back({s, t, w});
    }

    vector<vector<Weight>> dist;
    vector<vector<int>> inter; 
    if(!shortestPath(g,dist,inter)){
        cout << "NEGATIVE CYCLE" << endl;
    }else{
        for(int i=0; i<v; i++){
            for(int j=0; j<v; j++){
                if(dist[i][j]==INF){
                    cout << "INF";
                }else{
                    cout << dist[i][j];
                }
                if(j!=v-1) cout << " ";
            }
            cout << endl;
        }
    }
}


Measured memory_bytes: 3264
def between(num)
  if (1<=num&&num<=9)then
    res=true
  else
    res=false
  end
  return res
end

N=gets.to_i
res="No"
for i in 1..9 do
  num=N/i
  if(N%i==0 && between(num))then
    res="Yes"
    
  end
end
puts(res)

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

using namespace std;

#define sim template <class c
#define ris return *this
#define dor > debug &operator<<
#define eni(x)                                                                        \
	sim > typename enable_if<sizeof dud<c>(0) x 1, debug &>::type operator<<(c i) \
	{
sim > struct rge
{
	c b, e;
};
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c *x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug
{
#ifdef LOCAL
	~debug()
	{
		cerr << endl;
	}
	eni(!=) cerr << boolalpha << i;
	ris;
} eni(==) ris << range(begin(i), end(i));
}
sim, class b dor(pair<b, c> d)
{
	ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d)
{
	*this << "[";
	for (auto it = d.b; it != d.e; ++it)
		*this << ", " + 2 * (it == d.b) << *it;
	ris << "]";
}
#else
	sim dor(const c &)
	{
		ris;
	}
#endif
}
;
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define forn(i, n) for (ll i = 0; i < int(n); i++)
#define rfor(n, i) for (ll i = (n - 1); i >= 0; --i)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()
#define len(V) (int)V.size()
#define ll long long
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define endl '\n'
#define M_PI 3.14159265358979323846
#define EPS 1e-7

int cnt = 0;


void solve()
{
	int n, m; cin >> n >> m;
	multiset<string> s;
	forn(i, n)
	{
		string p; cin >> p;
		s.insert(p);
	}
	for(auto x: s) cout << x;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	solve();
}


Measured memory_bytes: 3660
H, W = map(int, input().split())
if H == 1 or W == 1:
    print(1)
else:
    if W % 2 == 0:
        r = W // 2
        print(r * H)
    else:
        r1 = W // 2 + 1
        r2 = W // 2 
        c = 0
        for i in range(H):
            if i % 2 == 0:
                c += r1
            else:
                c += r2
        print(c)

Measured memory_bytes: 40172
#include <bits/stdc++.h>
using namespace std;
int main ()
{
    int n;
    cin>>n;
    getchar();
    while (n--)
    {
        string ara="",ara2="",res="";
        getline(cin,ara);
        getline(cin,ara2);

        if (ara.length()>ara2.length())
            swap(ara,ara2);

        int l1,l2;
        l1=ara.length();
        l2=ara2.length();

        reverse(ara.begin(),ara.end());
        reverse(ara2.begin(),ara2.end());

        int i,sum,carry=0;
        for (i=0;i<l1;i++)
        {
            sum=((ara[i]-'0')+(ara2[i]-'0')+carry);
            res.push_back((sum%10)+'0');
            carry=sum/10;
        }
        for (i=l1;i<l2;i++)
        {
            sum=(ara2[i]-'0')+carry;
            res.push_back((sum%10)+'0');
            carry=sum/10;
        }
        if (carry!=0)
            res.push_back(carry+'0');
        reverse (res.begin(),res.end());
        if (res.length()<=80)
            cout<<res;
        else
            cout<<"overflow";
        cout<<endl;
    }
    return 0;
}


Measured memory_bytes: 3128
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

namespace A_DDCC2020
{
    class MainClass
    {

        static int[] s;

        public static void Main(string[] args)
        {
            s = Array.ConvertAll(ReadLine().Split().ToArray(), int.Parse);
            int x = s[0];
            int y = s[1];
            if(x==1&&y==1){
                WriteLine(1000000);
                return;
            }
            int ans = 0;
            if(x<4){
                if(x==3){
                    ans+=100000;
                }else if(x==2){
                    ans+=200000;
                }else if(x==1){
                    ans+=300000;
                }
            }
            if(y<4){
                if(y==3){
                    ans+=100000;
                }else if(y==2){
                    ans+=200000;
                }else if(y==1){
                    ans+=300000;
                }
            }
            WriteLine(ans);
        }
    }
}


Measured memory_bytes: 13268
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <list>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<P,ll> PPI;
typedef pair<ll,P> PIP;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vp;
#define PQ(T) priority_queue<T,vector<T>,greater<T>>
#define PQ2(T) priority_queue<T>
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
#define REP(i,a,b) for(ll (i)=a;(i)<(ll)(b);++(i))
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n+1)
#define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d))
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset((m),(v),sizeof(m))
#define chmin(x,y) ((x)=min((x),(y)))
#define chmax(x,y) ((x)=max((x),(y)))
#define fst first
#define snd second
#define UNIQUE(x) (x).erase(unique(all(x)),(x).end())
#define DEBUG(x) cerr<<"line ("<<__LINE__<<")  "<<#x<<": "<<x<<endl;
template<class T> ostream &operator<<(ostream &os, const vector<T> &v){int n=v.size();rep(i,n)os<<v[i]<<(i==n-1?"":" ");return os;}
#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);

#define N 100010
ll d[N];
ll c[16], dp[1<<16];

int main(){
	INIT;
	int n;
	cin>>n;
	rep(i, n-1){
		ll x, y, z;
		cin>>x>>y>>z;
		d[x] ^= z;
		d[y] ^= z;
	}
	rep(i, n) c[d[i]]++;
	ll res = 0, s = 0;
	for(int i = 1; i < 16; i++){
		res += c[i]/2;
		c[i] %= 2;
		if(c[i]) s |= 1<<i;
	}
	fill(dp, dp+(1<<16), INF);
	dp[0] = dp[1] = 0;
	rep(i, 16) rep(j, 16){
		if(i==j) continue;
		ll k = i^j;
		ll ij = (1<<i)|(1<<j);
		rep(b, 1<<16){
			if(b&ij) continue;
			if(b&(1<<k)) chmin(dp[b|ij], dp[b^(1<<k)]+2);
			else chmin(dp[b|ij], dp[b^(1<<k)]+1);
		}
	}
	res += dp[s];
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 1664
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
using ll=long long;
#define rep(i,a,b) for(ll i=a;i<ll(b);i++)
#define repr(i,a,b) for(ll i=a;i>=ll(b);i--)
#define endl "\n"
#define ALL(x) x.begin(),x.end()
#define ALLR(x) x.rbegin(),x.rend()
#define INF 1e9
#define DEBUG(x) cout<<"debug: "<<x<<endl

string s, t, ans;
int main() {
    cin >> s >> t;

    int sl = s.length();
    int tl = t.length();

    if(sl < tl){
        cout << "UNRESTORABLE" << endl;
        return 0;
    }

    if(sl == tl){
        rep(i, 0, sl){
            if(s[i] == '?') s[i] = t[i];
        }
        if(s == t) cout << s << endl;
        else cout << "UNRESTORABLE" << endl;
        return 0;
    }

    reverse(ALL(s));
    reverse(ALL(t));

    bool found = false;
    rep(i, 0, sl - tl){
        rep(k, 0, tl){
            if(s[i+k] != t[k] && s[i+k] != '?'){
                found = false;
                break;
            }else found = true;
        }
        if(found) {
            rep(k, 0, tl){
                s[i+k] = t[k];
            }
            rep(k, 0, sl) if(s[k] == '?') s[k] = 'a';
            reverse(ALL(s));
            break;
        }
    }

    if(found) cout << s << endl;
    else cout << "UNRESTORABLE" << endl;

    return 0;
}


Measured memory_bytes: 3080
def inpl():
    return list(map(int, input().split()))


N = int(input())
TA = [inpl() for i in range(N)]

a, b = TA[0][0], TA[0][1]
for ta, ao in TA[1:]:
    if ta >= a and ao >= b:
        a = ta
        b = ao
    else:
        # elif ta < a and ao < b:
        tmp_a = -(-1 * a // ta)
        tmp_b = -(-1 * b // ao)
        tmp = max(tmp_a, tmp_b)
        a = ta * tmp
        b = ao * tmp
    # elif ta < a and ao >= b:

print(a + b)


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

using namespace std;

#define pb push_back

const int N = 2e3 + 5, inf = 1e9 + 123;
int n, ans = inf, cnt[N], mn[N], mx[N];
string s;
vector<int> gr[N];

void dfs (int u, int p) {
    cnt[u] = (s[u] == '1');
    mx[u] = 0;
    int ver = -1;
    for (int v : gr[u]) if (v != p) {
        dfs(v, u);
        cnt[u] += cnt[v];
        mx[u] += mx[v] + cnt[v];
        if (ver == -1 || mn[v] + cnt[v] > mn[ver] + cnt[ver]) ver = v;
    }
    if (ver != -1 && mn[ver] + cnt[ver] > mx[u] - mx[ver] - cnt[ver]) mn[u] = mn[ver] + cnt[ver] - (mx[u] - mx[ver] - cnt[ver]);
    else mn[u] = mx[u] % 2;
}

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

    cin >> n >> s; s = "@" + s;
    for (int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        gr[u].pb(v);
        gr[v].pb(u);
    }

    for (int i = 1; i <= n; ++i) {
        dfs(i, -1);
        if (!mn[i]) ans = min(ans, mx[i] / 2);
    }

    cout << (ans == inf ? -1 : ans);

    return 0;
}


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

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	if ((a < c && b > c) || (a > c && b < c)) puts("Yes");
	else puts("No");
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,k,b[100005],l;
long long dp[105][65005];
const int M=1e9+7;
int main(){
	scanf("%d %d",&n,&k);
	int z=1,q;
	while(z<=n){
		q=n/(n/z);
		b[++l]=q-z+1;
		z=q+1;
	}
	n=l;
	for(int i=1;i<=n;++i){
		dp[1][i]=dp[1][i-1]+b[i];
	}
	for(int i=2;i<=k;++i){
		for(int o=1;o<=n;++o){
			dp[i][o]=(1ll*b[o]*dp[i-1][n-o+1]%M)+dp[i][o-1];
			if(dp[i][o]>=M)dp[i][o]-=M;
		}
	}
	printf("%lld",dp[k][n]);
}

Measured memory_bytes: 53248
process.stdin.resume();
process.stdin.setEncoding("utf8");

const reader = require("readline").createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];

reader.on("line", (line) => {
  lines.push(line);
});

reader.on("close", () => {
  const w = lines[0];
  let count = 0;
  for (let i = 1; i <= lines.length; i++) {
    const s = lines[i];
    if (s === "END_OF_TEXT") break;
    const ss = s.split(" ");
    for (let j = 0; j < ss.length; j++) {
      if (ss[j].toLowerCase() === w) count++;
    }
  }
  console.log(count);
});



Measured memory_bytes: 16256
#include <iostream>

int calc_sum(int x){
  int sumx = 0;
  while(x > 0){
    sumx += x % 10;
    x /= 10;
  }
  return sumx;
}

int main(){
  int n, a, b;
  std::cin >> n >> a >> b;
  int ans = 0;
  for(int i=1;i<=n;i++){
    int t = calc_sum(i);
    if(a <= t && t <= b)
      ans += i;
  }
  
  std::cout << ans << std::endl;
  return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(700000)

from collections import deque

N, u, v = map(int, input().split())
tree = deque([deque() for i in range(N+1)])

def dfs(s, dist, d=0, p=-1):
    dist[s] = d
    for tmp in tree[s]:
        if tmp != p:
            dfs(tmp, dist, d+1, s)

for i in range(N-1):
    A, B = map(int, input().split())
    tree[A-1].append(B-1)
    tree[B-1].append(A-1)

distT, distA = [0]*N, [0]*N

dfs(u-1, distT)
dfs(v-1, distA)

ans = 0
for i in range(N):
    if distT[i] < distA[i]:
        ans = max(ans, distA[i])
print(ans-1)

Measured memory_bytes: 170460
#include <cstdio>

using namespace std;

int main()
{
    int N, M;
    int P;
    long X;

    scanf("%d", &N);

    long T[N];

    int i, j;

    for (i = 0; i < N; i++) scanf("%ld", &T[i]);

    scanf("%d", &M);

    for (i = 0; i < M; i++) {
        scanf("%d %ld", &P, &X);

        int index = P - 1;
        long ans = 0;

        for (j = 0; j < N; j++) {
            if (j == index) {
                ans += X;
            } else {
                ans += T[j];
            }
        }

        printf("%ld\n", ans);
    }

    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define ll long long int
#define pr pair<ll, ll>
#define tp tuple<ll, ll, ll>
using namespace std;
long long int mod = 1e9 + 7;

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

    ll n;
    cin >> n;
    ll num = n - 1;
    ll ans = 0;
    for (ll i = 1; i * i <= num; i++)
    {
        if (num % i == 0)
        {
            if (num / i == i)
                ans++;
            else
                ans += 2;
        }
    }
    ans--;
    for (ll i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            ll val = i, temp = n;
            while (temp % val == 0)
                temp /= val;
            if (temp % val == 1)
                ans++;
            if (n / i != i)
            {
                ll val = n / i, temp = n;
                while (temp % val == 0)
                    temp /= val;
                if (temp % val == 1)
                    ans++;
            }
        }
    }
    ans++;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,k;
	cin>>n>>k;
	int arr[n];
	for(int i=0;i<n;i++){
		cin>>arr[i];
	}
	sort(arr,arr+n);
	int m=1<<30;
	for(int i=0;i<n-k+1;i++){
		m=min(m,arr[i+k-1]-arr[i]);
	}
	cout<<m<<endl;
	return 0;
}

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

#define FOR(i,a,b)  for(ll (i)=a;(i)<(b);++(i))
#define RFOR(i,a,b) for(ll (i)=a;(i)>=(b);--(i))
#define REP(i,n)    FOR(i,0,n)
#define RREP(i,n)   RFOR(i,n,0)
#define ALL(v)      (v).begin(),(v).end()
#define BIT(n)      (1LL<<(n))
#define IN(x,l,r)   ((l)<=(x)&&(x)<=(r))
#define LEN(s)      (string(s)).length()
#define NPOS        string::npos
#define SHOW(x)     cout<<#x<<" = "<<x<<endl
#define SORT(v)     sort(ALL(v))
#define SZ(v)       (ll)(v).size()
#define UNIQ(v)     SORT(v);(v).erase(unique(ALL(v)),(v).end())
#define PERM(v)     for(bool p=1;p;p=next_permutation(ALL(v)))
#define PQ(T)       priority_queue<T,vector<T>,greater<T>>

template<class T>string join(const vector<T>& v,string d=" ")
{stringstream s;REP(i,SZ(v))s<<d<<v[i];return s.str().substr(LEN(d));}

template<class T>ostream& operator<<(ostream& s,const vector<T>& v)
{s<<"{";if(SZ(v))s<<join(v,", ");s<<"}";return s;}

template<class T>bool contain(const string& s,const T& v)
{return s.find(v)!=NPOS;}

template<class T,class U>string& replace(string& s,const T& f,const U& t)
{for(auto p=s.find(f);p!=NPOS;p=s.find(f,p+LEN(t)))s.replace(p,LEN(f),t);}

const ll INF = 1e15;
const ll MOD = 1e9+7;
const double EPS = 1e-10;

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

int main() {
    string S; cin >> S;
    ll K; cin >> K;
    
    ll N = LEN(S);
    REP(i, N) if (S[i] != 'a') {
        if ('z' - S[i] + 1 <= K) {
            K -= 'z' - S[i] + 1;
            S[i] = 'a';
        }
    }
    
    K %= 26;
    string temp = "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz";
    S[N-1] = temp[S[N-1] - 'a' + K];
    
    cout << S << endl;
    
    return 0;
}


Measured memory_bytes: 512
#include <iostream>
using namespace std;
int main()
{
	int L,R,N,i,j,k,count=0;
	cin>>L>>R>>N;
	for(i=L;i<=R;i++)
	{
		if(i%N==0)
		count++;
	}
		cout<<count<<"\n";
		return 0;
}

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

#include <sstream>
#include <fstream>
#include <cmath>
#include <vector>


using namespace std;

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

	uint64_t X=0;
	cin >> X;

	uint64_t max = pow(10 , 9);
	uint64_t couter = 1;
	uint64_t sum = 0;
	vector<uint64_t> checker;
	while(1){
		sum += (couter++);
		if(sum > max) break;
		checker.push_back(sum);
	}

	//for(auto ch : checker) std::cout << ch << "\n";

	uint32_t ans;
	for(ans = 0 ; ans < checker.size() ; ans++){
		if(checker[ans] >= X ) break;
	}

	cout << ans+1 << "\n";
}


Measured memory_bytes: 892
#include <iostream>
#include <vector>
#include <algorithm>

using std::cin;
using std::cout;
using std::vector;



int main(int argc, char* argv[])
{
  std::ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int N, K;
  cin >> N >> K;

  vector<int> a(N);
  for (auto& v : a) cin >> v;

  vector<long long> s;
  s.reserve((N*(N+1)) / 2);
  for (int i = 0; i < N; ++i)
  {
    long long ss = 0;
    for (int j = i; j < N; ++j)
    {
      ss += a[j];
      s.push_back(ss);
    }
  }

  long long res = 0;
  for (int bit = 40; bit >= 0; --bit)
  {
    const long long pw = 1LL << bit;
    const int cnt = std::count_if(s.cbegin(), s.cend(), [pw](long long x){ return x & pw; });

    if (cnt >= K)
    {
      res |= pw;
      s.erase(
        std::remove_if(
          s.begin(),
          s.end(),
          [pw](long long x){ return (x & pw) == 0; }),
        s.end());
    }
  }
  cout << res << "\n";


  return 0;
}


Measured memory_bytes: 4224
#include <bits/stdc++.h>
#define MAX_N 100000
#define pb push_back
using namespace std;
vector<pair<int,int>> g[MAX_N];//tree
int N,root=0,parent[MAX_N],depth[MAX_N];
int q,r,d_max=0;

void dfs(int v,int p,int d){//v:current vertex ,p:parent of v,d:dpeth of v
    depth[v]=d;
            if(d>d_max){
            q=v;
            d_max=d;
        }
    for(int i=0;i<g[v].size();i++){
        if(g[v][i].first==p)continue;
        dfs(g[v][i].first,v,d+g[v][i].second);
    }
}

void add_edge(int u,int v,int c){
    g[u].pb({v,c});
    g[v].pb({u,c});
}

int main(void){
    // Here your code !
    cin>>N;
    for(int i=0;i<N-1;i++){
        int u,v,c;
        cin>>u>>v>>c;
        add_edge(u,v,c);
    }
    
    dfs(root,-1,0);
    dfs(q,-1,0);
    
    cout<<d_max<<endl;
}

Measured memory_bytes: 15180
#include <iostream>
#include <vector>
#include <set>
#include <map>
using namespace std;

#define div __nico_div
#define D(x) cerr << #x << "=" << x << endl
#define forn(i,n) for (int i = 0; i < int(n); i++)
typedef long long ll;

const int MOD = 998244353;

const int N = 2e5 + 10;

int n;
string x;
int cum[N], col[N];

void add(int &x, int y) {
    x += y;
    if (x >= MOD) x -= MOD;
}

set<int> div;
map<int,int> len;

void check(int d) {
    if (((2*n)%d == 0) && (n%d != 0)) div.insert(d);
}

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

bool check_col() {
    forn(i,n) if (col[i] != x[i]) return col[i] < x[i]; 
    return true;
}

int main() {
    cin >> n >> x;
    forn(i,n) x[i] -= '0';
    forn(i,n) {
        cum[i+1] = cum[i]*2 + x[i];
        cum[i+1] %= MOD;
    }
    for (int d = 1; d*d <= 2*n; d++) check(d), check(2*n/d);

    for (auto d : div) {
        int rem = gcd(d,n);
        len[d] = cum[rem];
        forn(i,n) col[i] = -1;
        forn(i,rem) {
            int j = i, c = x[i];
            while (col[j] == -1) {
                col[j] = c;
                j += d;
                if (j >= n) {
                    j %= n;
                    c = 1-c;
                }
            }
        }
        add(len[d], check_col());
    }

    for (auto lc : len) {
        int l,c; tie(l,c) = lc;
        for (int l2 = 2*l; l2 <= 2*n; l2 += l) {
            if (len.count(l2)) 
                add(len[l2], MOD - len[l]);
        }
    }

    int ans = 0;
    for (auto xy : len) {
        int x,y; tie(x,y) = xy;
        add(ans, ll(x)*y%MOD);
    }
    cout << ans << endl;
    return 0;
}


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

int main(){
  int n,c[26]={},kari=0,cnt=0;
  char s[310][310],a[310][310][310];
  bool fl=0,d[310][310]={},e[310]={};
  cin>>n;
  fr(i,n){
    fr(j,n) cin >>s[i][j];
  }
fr(k,n){
  fl=false;
  fr(i,n){
    fr(j,n){
      a[k][i][j]=s[(i+k)%n][j];
    }
  }
  fr(i,n){
    fr(j,n){
      if(a[k][i][j]==a[k][j][i]) fl=true;
      else{fl=false;break;}
    }
    if(fl==false) break;
  }
  if(fl) cnt++;
}
  cout<<n*cnt;
}


Measured memory_bytes: 29440
n, m = map(int, input().split())
h = list(map(int, input().split()))
way = [list(map(int, input().split())) for _ in range(m)]

ans = [0]*n
for w in way:
    a = w[0]
    b = w[1]
    if h[a-1] < h[b-1]:
        ans[a-1] += 1
    elif h[a-1] > h[b-1]:
        ans[b-1] += 1
    else:
        ans[a-1] += 1
        ans[b-1] += 1

count = 0
for a in ans:
    if a == 0:
        count += 1
print(count)

Measured memory_bytes: 31888
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader input =new BufferedReader (new InputStreamReader (System.in));
		String str = input.readLine( );
		String[] strlist = str.split(" ");
		int n = Integer.parseInt(strlist[0]);
		int k = Integer.parseInt(strlist[1]);

		int answer = k;

		for(int i=0; i<n-1; i++){
			answer = answer * (k-1);
		}

		System.out.println(answer);

	}

}


Measured memory_bytes: 8148
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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; }
//---------------------------------------------------------------------------------------------------
vector<pair<char, int>> runLengthEncoding(string s) {
	int n = s.length();

	vector<pair<char, int>> res;
	char pre = s[0];
	int cnt = 1;
	rep(i, 1, n) {
		if (pre != s[i]) {
			res.push_back({ pre, cnt });
			pre = s[i];
			cnt = 1;
		}
		else cnt++;
	}

	res.push_back({ pre, cnt });
	return res;
}
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/






int N, K; string S;
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> K >> S;

	auto blocks = runLengthEncoding(S);
	int M = blocks.size();
	int ans = 0;
	int sm = 0;
	int L = 0;
	int zero = 0;
	rep(R, 0, M) {
		sm += blocks[R].second;
		if (blocks[R].first == '0') zero++;

		while (K < zero) {
			sm -= blocks[L].second;
			if (blocks[L].first == '0') zero--;
			L++;
		}

		chmax(ans, sm);
	}
	cout << ans << endl;
}


Measured memory_bytes: 1724
import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner scan = new Scanner(System.in); int[] x = new int[3]; x[0] = scan.nextInt(); x[1] = scan.nextInt(); x[2] = scan.nextInt(); java.util.Arrays.sort(x); System.out.println(x[0]+" "+x[1]+" "+x[2]); } }


Measured memory_bytes: 26172
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main() {
  int r,g,b;
  cin>>r>>g>>b;
  if ((g*10+b)%4==0){
    cout<<"YES"<<endl;
  }
  else{
    cout<<"NO"<<endl;
  }
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
#include<bits/stdc++.h>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define pll pair<ll,ll>
#define pint pll
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

struct edge{int to,cost;};
int V,V2;
vector<edge> G[100010],G2[100010];
ll d[100010],d2[100010];
 
void dijkstra(int s){
  priority_queue<pint,vector<pint>,greater<pint>> que;
  fill(d,d+V,longinf);
  d[s]=0;
  que.push(pint(0,s));
  
  while(!que.empty()){
    pint p=que.top(); que.pop();
    int v=p.second;
    if(d[v]<p.first)continue;
    rep(i,G[v].size()){
      edge e=G[v][i];
      if(d[e.to]>d[v]+e.cost){
        d[e.to]=d[v]+e.cost;
        que.push(pint(d[e.to],e.to));
      }
    }
  }
}

void dijkstra2(int s){
  priority_queue<pint,vector<pint>,greater<pint>> que;
  fill(d2,d2+V2,longinf);
  d2[s]=0;
  que.push(pint(0,s));
  
  while(!que.empty()){
    pint p=que.top(); que.pop();
    int v=p.second;
    if(d2[v]<p.first)continue;
    rep(i,G2[v].size()){
      edge e=G2[v][i];
      if(d2[e.to]>d2[v]+e.cost){
        d2[e.to]=d2[v]+e.cost;
        que.push(pint(d2[e.to],e.to));
      }
    }
  }
}

int main(){
  cin >> V;
  int u,v;
  cin >> u >> v;
  u--,v--;
  int a[V-1],b[V-1];
  rep(i,V-1){
    cin >> a[i] >> b[i];
    a[i]--,b[i]--;
    G[a[i]].push_back({b[i],1});
    G[b[i]].push_back({a[i],1});
  }
  dijkstra(v);
  int dist=(d[u]+1)/2;
  V2=V;
  rep(i,V-1){
    if(d[a[i]]>=dist && d[b[i]]>=dist){
      G2[a[i]].push_back({b[i],1});
      G2[b[i]].push_back({a[i],1});
    }
  }
  dijkstra2(u);
  ll ans=0;
  rep(i,V2){
    if(d2[i]<longinf)ans=max(ans,d[i]-1);
  }
  cout << ans << endl;
return 0;}

Measured memory_bytes: 16288
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MOD1 1000000007
#define MOD2 998244353
#define LIMIT1 200002
#define LIMIT2 500002
typedef long long ll;
typedef long double ld;
typedef const void cv;
#define rep(i,n) for((i)=0;(i)<(n);(i)++)
#define per(i,n) for((i)=(n)-1;(i)>=0;(i)--)
#define max(a,b) ((a)>(b) ? (a) : (b))
#define min(a,b) ((a)<(b) ? (a) : (b))
#define zt(a,b) (max((a),(b))-min((a),(b)))
#define absl(v) labs((v))
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll nPr(int n,int r){ll i,result=1;rep(i,r){result*=(ll)(n-i);}return result;}
ll nCr(int n,int r){ll i,result=1;if(n<r) return 0;rep(i,min(r,n-r)){result*=(ll)(n-i);result/=(ll)(i+1);}return result;}
#define nHr(n,r) nCr((int)((n)+(r)+1),(int)(r))
#define sankaku(x) (((x)*((x)+1))/2)
int dx[8]={1,0,-1,0,1,-1,-1,1},dy[8]={0,1,0,-1,1,1,-1,-1};
int upint(cv *a, cv *b) { return *(int *)a < *(int *)b ? -1 : *(int *)a > *(int *)b ? 1 : 0; }
int downint(cv *a, cv *b) { return *(int *)a < *(int *)b ? 1 : *(int *)a > *(int *)b ? -1 : 0; }
int upchar(cv *left, cv *right) {return strcmp((char *)left,(char *)right);}
int downchar(cv *left, cv *right) {return strcmp((char *)right,(char *)left);}
void tmpInit(int *c,ll m) {ll i;rep(i,m) c[i]=i;}
ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1){
            res *= a; if(mod>=1) res %= mod;
        }
        a *= a; if(mod>=1) a %= mod;
        n >>= 1;
    }
    return res;
}
void initialize(){
    
}
int main(void){
  initialize();
  ll n,m,i,j,k,result=0;
  int a[LIMIT2]={0};
  char s[LIMIT1];
  
  scanf("%s",s);
  n = strlen(s);
  
  rep(i,n){
    if(s[i]=='?') s[i]='D';
  }
  printf("%s",s);
  return 0;
}

Measured memory_bytes: 1928
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

class MainClass
{
    static void Main()
    {
        var abc = ReadLine().Split().Select(int.Parse).ToArray();
        int a = abc[0];
        int b = abc[1];
        int c = abc[2];
        var K = int.Parse(ReadLine());

        for (int i = 0; i < K; i++)
        {
            if (b >= c) c *= 2;
            else if (a >= b) b *= 2;
        }
        if (a < b && b < c) WriteLine("Yes");
        else WriteLine("No");
    }
}


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

int n, k, c;
string s;

bool solve(void)
{
	int i, j;
	int ans = 0;
	for (i = 0; i < n; i++) {
		if (s[i] == 'o') {
			ans++;
			if (ans == k) {
				return true;
			}
			i = i + c;
		}
	}
	return false;
}

int main()
{
	int i, j;
	
	cin >> n >> k >> c;
	cin >> s;

	int *mae = new int[k];
	int *usiro = new int[k];

	mae[0] = usiro[0] = 0;
	j = 0;

	for (i = 0; i < n; i++) {
		if (s[i] == 'o') {
			if (j < k) {
				mae[j] = i;
				j++;
			}
			i = i + c;
		}
	}

	j = k-1;
	for (i = n - 1; i >= 0; i--) {
		if (s[i] == 'o') {
			if (j >= 0) {
				usiro[j] = i;
				j--;
			}
			i = i - c;
		}

	}

	for (j=0; j<k; j++) {
		if (mae[j]==usiro[j]){
			cout << mae[j]+1 << endl;
		}
	}

	return 0;
}


Measured memory_bytes: 3332
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Globalization;

namespace 練習１
{
    class Program
    {
        static void Main(string[] args)
        {
            var x1 = Console.ReadLine().Split(' ');
            var x2 = new int[2];
            for(var i = 0; i < x1.Length; i++)
            {
                x2[i] = int.Parse(x1[i]);
            }

            var y1 = Console.ReadLine().Split(' ');
            var y2 = new int[1000];
            for(var i = 0; i < x2[0]; i++)
            {
                y2[i] = int.Parse(y1[i]);
            }

            var total = y2.Sum();
            var vote = total * (1 / (4 * (double)x2[1]));
            int count = 0;

            for(var i = 0; i < x2[0]; i++)
            {
                if (y2[i] >= vote) 
                {
                    count++;
                }
            }

            if (count >= x2[1])
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }
}

Measured memory_bytes: 13268
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(V, v) for (auto&& V : v)
#define all(x) (x).begin(), (x).end()
using lint = long long;
const int INF = 1 << 29;
const double EPS = 1e-9;
using namespace std;

int main(void) {
  int h, w;
  cin >> h >> w;
  string s, tmp;
  rep(i, h) {
    cin >> tmp;
    s += tmp + "\n" + tmp + "\n";
  }
  cout << s << endl;
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
//#include <regex>

/* g++ -g -std=c++0x */
/* g++ -g -std=c++11 */

using namespace std;

// freopen("input.txt", "rt", stdin);
// freopen("output.txt", "wt", stdout);

#define ALL(c)          (c).begin(), (c).end()
#define ALLR(c)         (c).rbegin(), (c).rend()
#define FOR(i,a,b)      for (int i=(a); i < (b); ++i)
#define FORR(i,a,b)     for (int i=(a); i > (b); --i)
#define FOR_ALL(i,c)    for (__typeof((c).begin()) i=(c).begin();   \
                             i != (c).end(); ++i)
#define FOR_ALLR(i,c)   for (__typeof((c).rbegin()) i=(c).rbegin(); \
                             i != (c).rend(); ++i)
#define SZ(array)       (sizeof(array)/sizeof(array[0]))
#define lc(x)           (x<<1)     /* 2*x */
#define rc(x)           (x<<1 | 1) /* 2*x+1 */
#define lowbit(x)       (x & (-x)) /* 0b10100 -> 0b100 */

typedef long long       LL;
typedef map<int,int>    MII;
typedef pair<int,int>   PII;
typedef set<int>        SI;
typedef vector<bool>    VB;
typedef vector<double>  VD;
typedef vector<int>     VI;
typedef vector<string>  VS;

/* check if a key is in container C */
template <class C>
inline bool in_(const typename C::key_type& k, const C& A)
{ return A.find(k) != A.end(); }
inline bool in_(const string& s, const string& S)
{ return S.find(s) != string::npos; }

const int inf = 1e9;
const int maxn = 1e5+5;
int N,M, vis[maxn];
struct Point { int i,x,type; };

typedef bool (*cmpfn)(const Point&, const Point&);

bool cmp(const Point& a, const Point& b)
{
    if (a.x == b.x)
        return a.type > b.type;
    return a.x < b.x;
}

int main()
{
/* #ifndef ONLINE_JUDGE */
/*     freopen("foo", "rt", stdin); */
/* #endif */
    ios::sync_with_stdio(false);
    while (cin >> N >> M) {
        multiset<Point,cmpfn> P(cmp);
        for (int i = 0; i < M; i++) {
            Point a,b;
            cin >> a.x; a.i = i; a.type = 0;
            P.insert(a);
            cin >> b.x; b.i = i; b.type = 1;
            P.insert(b);
        }
        memset(vis,0,sizeof(vis));
        int ans = 0; queue<int> Q;
        FOR_ALL(i,P) if (!vis[i->i]) {
            if (i->type == 0)
                Q.push(i->i);
            else {
                if (Q.size())
                    ans++;
                while (Q.size()) {
                    const int x = Q.front(); Q.pop(); vis[x]++;
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 13312
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
0 0 3 4
1
2 5

output:
3.1200000000 4.1600000000
"""

import sys


class Segment(object):
    __slots__ = ('source', 'target')

    def __init__(self, source, target):
        self.source = complex(source)
        self.target = complex(target)


def dot(a, b):
    return a.real * b.real + a.imag * b.imag


def project(s, p):
    base_vector = s.target - s.source
    prj_ratio = dot(p - s.source, base_vector) / pow(abs(base_vector), 2)
    return s.source + base_vector * prj_ratio


def solve(_prj_points):
    for point in _prj_points:
        xp, yp = map(int, point)
        p = xp + yp * 1j
        prj = project(prj_segment, p)
        print('{real:.10f} {imag:.10f}'.format(real=prj.real, imag=prj.imag))

    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()

    line = tuple(map(int, _input[0].split()))
    q_num = int(_input[1])
    p1, p2 = (x + y * 1j for x, y in zip(line[::2], line[1::2]))
    prj_segment = Segment(p1, p2)

    prj_points = map(lambda x: x.split(), _input[2:])

    solve(prj_points)

Measured memory_bytes: 7788
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm> 
using namespace std; 

int main()
{
    int n;
    double m;
    
    cin>>n;
    m=6.28318530717958623200*n;
    printf("%.2lf",m);
    
    
    return 0;
}


Measured memory_bytes: 3752
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

#define INF 999999

int n, k;
int color[10010], d[10010];
vector<pair<int, int> > adj[INF];

int dijkstra(int s)
{
    priority_queue<pair<int, int> > q;
    q.push(make_pair(0, s) );
    for(int i = 0; i < n; i ++)
    {
        d[i] = INF;     //距离初始化
    }
    d[s] = 0; //第一个点到它本身距离是零
    
    while(!q.empty() )
    {
        pair<int, int> t = q.top();
        q.pop();
        int u = t.second;
        color[u] = 1;
        
        
        for(int i = 0; i < adj[u].size(); i ++)
        {
            int v = adj[u][i].first;
            if(color[v] == 1)//被染过色了，跳过
                continue;
            if(d[v] > d[u] + adj[u][i].second)
            {
                d[v] = d[u] + adj[u][i].second;
                q.push(make_pair(-d[v], v) );
            }
        }
    }
    return 0;
}

int main(void)
{
    scanf("%d", &n);
    int u, k, v, c;
    for(int i = 0; i < n; i ++)
    {
        scanf("%d%d", &u, &k);
        for(int j = 0; j < k; j ++)
        {
            scanf("%d%d", &c, &v);
            adj[u].push_back(make_pair(c, v));
        }
    }
    dijkstra(0);
    
    for(int i = 0; i < n; i ++)
    {
        if(d[i] != INF)
            printf("%d %d", i, d[i]);
        printf("\n");
    }
    return 0;
}


Measured memory_bytes: 31264
#include<bits/stdc++.h>
#define ll long long
#define rgi register int
#define rgl register ll
#define int ll
#define maxn 100005
#define mod 998244353LL
#define inf 1000000007LL
namespace lib
{
	using namespace std;
	class fastio
	{
		private:
			#define _NUMLEN 111
			char _num[_NUMLEN],_ch;
			int _f,_head;
			bool _useSTD;
		public:
			inline void ioSTD()
			{
				_useSTD=1;
				ios::sync_with_stdio(false);
				cin.tie(0),cout.tie(0);
			}
			inline void gc(char & _c)
			{
				if(_useSTD)cin>>_c;
				else _c=getchar();
			}
			inline void pc(char _c)
			{
				if(_useSTD)cout<<_c;
				else putchar(_c);
			}
			template<typename _T> inline fastio & operator - (_T & _x)
			{
				if(_useSTD)cin>>_x;
				else
				{
					_x=0;
					while(!isdigit(_ch)) _f|=_ch=='-',gc(_ch);
					while(isdigit(_ch)) _x=(_x<<1)+(_x<<3)+(_ch^48),gc(_ch);
					_f&&(_x=-_x,_f=0);
				}
				return *this; 
			}
			template<typename _T> inline fastio & operator + (_T _x)
			{
				if(_useSTD)cin>>_x;
				else
				{
					_T _k;
					if(_x==0) {pc('0'),pc(' ');return *this;}
					if(_x<0) pc('-'),_x=-_x;
					while(_x>0) _k=_x/10,++_head,_num[_head]=(_x-(_k<<1)-(_k<<3))^48,_x=_k;
					while(_head>0) pc(_num[_head]),--_head;
					pc(' ');
				}
				return *this; 
			}
			template<typename _T> inline fastio & operator >> (_T & _x) {cin>>_x;return *this;}
			template<typename _T> inline fastio & operator << (_T _x) {cout<<_x;return *this;}
			#define endln pc('\n')
		fastio() {_f=0,_head=0,_useSTD=0,_ch=' ';}
	}io;
	inline void fileio(string _r,string _w)
	{
		if(_r[0]!='-')freopen(_r.c_str(),"r",stdin);
		if(_w[0]!='-')freopen(_w.c_str(),"w",stdout);
	}
	#define mem(_x,_set) memset(_x,_set,sizeof(_x))
}using namespace lib;

int a[maxn];
signed main()
{
	// fileio("tt.in","tt.out");
	io.ioSTD();
	int n,m,lcm=1,x;
	cin>>n>>m;
	for(rgi i=1;i<=n;++i)
	{
		cin>>a[i];
		a[i]/=2;
		lcm=lcm*a[i]/__gcd(lcm,a[i]);
		if(lcm>m)
		{
			cout<<0;
			return 0;
		}
	}
	// cout<<lcm<<" ";
	for(x=0;lcm%(1LL<<x)==0;++x);
	--x;
	for(rgi i=1;i<=n;++i)
		if(a[i]%(1LL<<x)!=0)
		{
			cout<<0;
			return 0;
		}
	cout<<(m+lcm)/(lcm*2);
	return 0;
}

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

int main()
{
    int n;
    cin>>n;
    int ar[n+1];
    for(int i=1;i<=n;i++)
        cin>>ar[i];
    int cnt=0,j=1;
    for(int i=1;i<=n;i++)
    {
        if(ar[i]==j)
        {
            cnt++;
            j++;
        }
    }
    if(n-j+1==n)
        cout<<-1<<endl;
    else
        cout<<n-j+1<<endl;
    return 0;
}


Measured memory_bytes: 4420
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //これつけるとA[N]でもいいらしい
//for文のマクロ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define big 1000000007
#define all(a) sort((a).begin(),(a).end()) //ソートのマクロ
#define Re(a) reverse((a).begin(),(a).end())
#define YN(a) if(a){cout<<"Yes"<<endl;}else cout<<"No"<<endl;//条件によってYes、Noを出力する
const int MOD=1000000007;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //cin,coutの高速化
    int64_t n,d,a;
    cin>>n>>d>>a;
    vector<pair<int64_t,int64_t>> p(n);
    rep(i,n){
        int x,h;
        cin>>x>>h;
        p[i] = make_pair(x,h);
    }
    all(p);
    int R=0;
    vector<int> r(n);
    rep(i,n){
        while(R<n && p[R].first<=p[i].first+2*d){
            R++;
        }
        r[i] = R;
        //cout<<i<<" "<<r[i]-1<<endl;
    }
    int64_t ans=0;
    vector<int64_t> damage(n+1,0);
    queue<pair<int64_t,int64_t>> q;
    int64_t sub=0;
    /*damage[0] = (p[0].second+a-1)/a*a;
    cout<<damage[0]<<endl;*/
    rep(i,n){
        sub=0;
        while(!q.empty()){
            if(i>=q.front().first){
                sub += q.front().second;
                q.pop();
            }
            else{
                break;
            }
        }
        if(i!=0){
            damage[i] += damage[i-1];
            damage[i] -= sub;
        }
        p[i].second -= damage[i];
        int64_t add = (p[i].second+a-1)/a;
        if(p[i].second<=0){
            add=0;
        }
        damage[i] += add*a;
        //cout<<damage[i]<<" ";
        q.push(make_pair(r[i],add*a));
        ans += add;
        //cout<<bomb<<"で"<<(h+a-1)/a<<"回爆破"<<endl;
    }/*
    rep(i,n){
        cout<<damage[i]<<" ";
    }*/
    cout<<ans<<endl;
}


Measured memory_bytes: 9088
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m;
  cin>>n>>m;
  map<int,int> mp;
  bool f = 0;
  for(int i = 0; i < m; i++){
  	int si,ci;
    cin>>si>>ci;
    
    if(mp.count(si)){
    	if(mp[si]!=ci){
        	f = 1;
        }
    }
    mp[si] = ci;  
  }
  if(mp.count(1)){
  	if(mp[1] == 0 && n!=1){
    	f = 1;
    }
  }
  else {
    if( n == 1) {
      mp[1] = 0;
    }
    else
    mp[1] = 1;
  }
  if(f==1){
  	cout<<"-1"<<"\n";
  }
  else{
   for(int i = 1; i <= n; i++){
  	cout<<mp[i];
   }
  }
  return 0;
}

Measured memory_bytes: 256
N,T=map(int,input().split())
alist=list(map(int,input().split()))
#print(alist)

arlist=alist[:]
for i in reversed(range(N-1)):
  arlist[i]=max(arlist[i],arlist[i+1])  
#print(arlist)

max_diff=0
for i in range(N-1):
  diff=arlist[i+1]-alist[i]
  max_diff=max(max_diff,diff)

max_diff_cnt=0
for i in range(N-1):
  diff=arlist[i+1]-alist[i]
  if diff==max_diff:
    max_diff_cnt+=1
#print(max_diff,max_diff_cnt)

print(max_diff_cnt)

Measured memory_bytes: 15020
#include<iostream>
#define _w_ true
using namespace std;

int main(){
  int n,aizu[20],in;
 
  while(_w_){
    cin >> n;
    if(n == 0)break;
 for(int i=0;i<20;i++)aizu[i]=0;
    while(n-- > 0){
      cin >> in;
      aizu[in]++;
    }
    for(int i=0;i<=9;i++){
      if(aizu[i] == 0)cout << "-" << endl;
      else {
	for(int j=0;j<aizu[i];j++){
	  cout << "*";
	}
	cout << endl;
      }
    }


  }
  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>
#include <stack>

using namespace std;

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

const ll mod = 1000000007;

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

  int n, a, b;
  cin >> n >> a >> b;
  vector<ll> h(n);
  for (auto &x: h) cin >> x;

  sort(h.rbegin(), h.rend());

  ll delta = a - b;

  ll left = 0;
  ll right = 1000000007;
  while (left < right) {
    ll center = (left + right) / 2;
    ll damage = b * center;
    ll hit = 0;
    for (int i = 0; i < n; i++) {
      ll remaining = h[i] - damage;
      if (remaining > 0) hit += (remaining + delta - 1) / delta;
    }
    if (hit <= center) right = center;
    else left = center + 1;
  }

  ll ans = left;

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define invrepr(i,a,b) for(int i=b-1;i>=a;i--)
#define invrep(i,n) invrepr(i,0,n)
#define repitr(itr,a) for(auto itr=a.begin();itr!=a.end();++itr)
#define P pair<int,int>
const int MOD=1e9+7;
const int INF=2e9;
 
 
int main() {
    ios_base::sync_with_stdio(false);
 
    int h,w;
    cin >> h >> w;
    vector<vector<char>> ans(h+2,vector<char>(w+2,'#'));
    rep(i,h) {
        rep(j,w) cin >> ans[i+1][j+1];
    }
    rep(i,h+2) {
        rep(j,w+2) cout << ans[i][j];
        cout << endl;
    }
 
    return 0;   
}

Measured memory_bytes: 256
x1,y1,x2,y2 = [int(i) for i in input().split()]

height = y2 - y1
width = x2 - x1

x3 = x2 - height
x4 = x3 - width
y3 = y2 + width
y4 = y3 - height

print(x3,y3,x4,y4)

Measured memory_bytes: 9096
#include<stdio.h>
#include<string.h>
int gcd(long long int x, long long int y){
    if (y == 0) return x;
    else        return gcd(y, x % y);
}
int main(){
    long long int a,b,ans,ansb;
    scanf("%lld %lld",&a,&b);
    ans=gcd(a,b);
    ansb=a*b;
    ansb=ansb/ans;
    printf("%lld",ansb);
    return 0;
}

Measured memory_bytes: 128
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <utility>
#include <functional>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_map>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
const int INF = (1<<30);
const int MOD = 1000000007;
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() {
    int n,q;
    cin >> n >> q;
    vector<int> A[n];
    vector<string> ans;
    rep(i, q){
        int a,b,c;
        cin >> a;
        switch (a)
        {
        case 0:
            cin >> b >> c;
            A[b].push_back(c);
            break;
        case 1:{
            cin >> b;
            int N = A[b].size();
            string s;
            rep(i, N) s.append(to_string(A[b][i]) + " ");
            if(s.size() > 0)s.pop_back();
            ans.push_back(s);
            break;
        }
        case 2:
            cin >> b;
            A[b].clear();
            break;
        }
    }
    int N = ans.size();
    rep(i, N) cout << ans[i] << endl;
    return 0;
}


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

using pii = pair<int, int>;

int main() {
  int n;
  cin >> n;
  vector<pii> r(n);
  for (int i = 0; i < n; i++) {
    int x, l;
    cin >> x >> l;
    r[i].first = x + l;
    r[i].second = x - l;
  }
  sort(r.begin(), r.end());
  int ans = 0, border = -(1 << 30);
  for (auto p : r) {
    int a, b;
    tie(b, a) = p;
    if (a >= border) {
      ans += 1;
      border = b;
    }
  }
  cout << ans << '\n';
}

Measured memory_bytes: 4016
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define SIZE 200005

int N,K,C;
int L[SIZE],R[SIZE];
char buf[SIZE];


int main(){

	scanf("%d %d %d",&N,&K,&C);
	scanf("%s",buf);

	int index_L = 0;
	int skip = 0;

	for(int i = 0; buf[i] != '\0'; i++){
		if(buf[i] == 'o' && skip == 0){

			L[index_L++] = i;
			skip = C;
		}else{
			if(skip > 0){

				skip--;
			}
		}
	}

	if(index_L > K){

		return 0;
	}

	int index_R = index_L-1;
	skip = 0;
	for(int i = N-1; i >= 0; i--){
		if(buf[i] == 'o' && skip == 0){

			R[index_R--] = i;
			skip = C;
		}else{
			if(skip > 0){

				skip--;
			}
		}
	}

	for(int i = 0; i < index_L; i++){
		if(L[i] == R[i]){

			printf("%d\n",L[i]+1);
		}
	}

	return 0;
}


Measured memory_bytes: 3200
N = int(input())
A_list = list(map(int, input().split()))

if any(a == 0 for a in A_list):
	print(0)
else:
	prod = 1
	for a in A_list:
		prod *= a
		if prod > 10 ** 18:
			prod = -1
			break
	print(prod)


Measured memory_bytes: 21644