akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define mod 1000000007
#define pie M_PI
#define maxm 2147483647
#define FOR(i,a,b) for(ll i=a;i<b;++i)
#define yes "YES\n"
#define no "NO\n"
#define ENDL "\n"

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
const long long maxs = 100000000;

void get(ll &num)
{
    scanf("%lld", &num);
}

void getd(ll &num1, ll &num2)
{
    scanf("%lld %lld", &num1, &num2);
}

void output(ll num)
{
    printf("%lld\n", num);
}
void outputd(ll num1, ll num2)
{
    printf("%lld %lld\n", num1, num2);
}

int main()
{

    // ios_base::sync_with_stdio(0);
    // cin.tie(NULL);
    // cout.tie(NULL);
    ll t = 1;
    ll n;
    while(t--)
    {
        get(n);
        int num = ceil((double) n / 1000);

        output(num * 1000 - n);

    }


}


Measured memory_bytes: 3816
import heapq


def dijkstra(g: list, start, goal=None):
    num = len(g)          # グラフのノード数
    dist = [float('inf') for i in range(num)]

    dist[start] = 0
    # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
    q = []
    heapq.heappush(q, (0, start))  # 始点をpush

    while q:
        prov_cost, src = heapq.heappop(q)  # pop
        # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
        if dist[src] < prov_cost:
            continue
        # 他の頂点の探索
        for node, cost in g[src]:
            if dist[node] > dist[src] + cost:
                dist[node] = dist[src] + cost
                heapq.heappush(q, (dist[node], node))
    return dist


n, m = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(n - 1):
    g[i + 1].append((i, 0))
for i in range(m):
    l, r, c = map(int, input().split())
    g[l - 1].append((r - 1, c))
d = dijkstra(g, 0)
if d[n - 1] == float('inf'):
    print(-1)
else:
    print(d[n - 1])


Measured memory_bytes: 84384
<?php
fscanf(STDIN, "%d", $n);
fscanf(STDIN, "%d", $k);
$x = fgets(STDIN);
$x_arr = explode(" ", $x);
$ret = [];
foreach($x_arr as $v) {
    $a = $v * 2;
    $b = ($k - $v) * 2;
    $ret[] = ($a > $b) ? $b : $a;
}
echo array_sum($ret). "\n";
//var_dump($x_arr);

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

typedef long long ll;

const int Maxn = 200005;

int n;
int a[Maxn];
ll res;

int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	int cur = 0, r = 0;
	for (int i = 0; i < n; i++) {
		while (r < n && (cur & a[r]) == 0) {
			cur ^= a[r]; r++;
		}
		res += r - i;
		cur ^= a[i];
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 1024
import sys
sys.setrecursionlimit(1000000)
def main():
    n, m = [int(x) for x in input().split()]
    global dp
    dp = [-1]*n
    grafo = [[] for _ in range(n)]

    for _ in range(m):
        x, y = [int(x) for x in input().split()]
        x -= 1
        y -= 1

        grafo[x].append(y)

    resp = 0
    for u in range(n):
        resp = max(dfs(u, grafo), resp)

    print(resp)
        

def dfs(u, grafo):
    global dp

    if len(grafo[u]) == 0:
        dp[u] = 0
        return dp[u]

    if dp[u] != -1:
        return dp[u]


    for v in grafo[u]:
        dp[u] = max(dfs(v, grafo) + 1, dp[u])

    return dp[u]
        
main()

Measured memory_bytes: 113864
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n,k,counter;
    cin>>n>>k;
    counter=k;
        for(int j=1;j<n;j++)
        {
         counter=counter*(k-1);
        }
    cout<<counter<<endl;
    return 0;

}


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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ALL(a)     (a).begin(),(a).end()
#define VI         vector<int>
#define MOD 1000000007

using ll = long long int;
using P = pair<int,int>;

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; }

const ll INF=(ll)1e19;
//const int INF=(1<<30);
//const int INF=(1<<29);

int main(){
  int N,T;
  cin >> N >> T;
  VI a(N);
  REP(i,N)cin >> a[i];

  int mi=(1<<30);
  map<int, int> mp;
  REP(i,N){
    if(mi > a[i]){
      mi = a[i];
    }else{
      mp[a[i]-mi]++;
    }
  }

  int ans;
  int ma=-1;
  for(auto v: mp){
    if(ma < v.first){
      ma = v.first;
      ans = v.second;
    }
  }
  cout << ans << endl;
}



Measured memory_bytes: 5376
import java.util.*;
import java.io.*;
class Main {
	public static void main(String...args)throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] zahyos = br.readLine().split(" ");
		double[] coor = new double[4];
		coor[0] = Double.valueOf(zahyos[0]); 
		coor[1] = Double.valueOf(zahyos[1]); 
		coor[2] = Double.valueOf(zahyos[2]); 
		coor[3] = Double.valueOf(zahyos[3]); 
		double a = Math.pow(coor[2] -coor[0] , 2);
		double b = Math.pow(coor[3] -coor[1] , 2);
		double c = a + b;
		double hypo = Math.sqrt(c);
		System.out.println(hypo);
	}
}



Measured memory_bytes: 24416
#include <algorithm>
#include <iostream>
#include <cstdio>

using namespace std ;

const int MAXN=1e5+100;

struct Query
{
	int u , v ;
};
Query q[MAXN];
int n , m ;

inline bool cmp ( Query A , Query B )
{
	if ( A.u==B.u ) return A.v<B.v;
	return A.u<B.u;
}

int main ()
{
	int i ;
	scanf("%d%d",&n,&m);
	for ( i=1 ; i<=m ; i++ ) scanf("%d%d",&q[i].u,&q[i].v);
	sort(q+1,q+m+1,cmp);
	int l=q[1].u , r=q[1].v ;
	int res=1;
	// for ( i=1 ; i<=m ; i++ ) printf("%d %d\n",q[i].u,q[i].v);
	for ( i=2 ; i<=m ; i++ )
	{
		if ( q[i].u>l && q[i].u<r ) 
		{
			l=q[i].u;
			if ( q[i].v<r ) r=q[i].v;
		}
		else if ( q[i].u>=r ) res++,l=q[i].u,r=q[i].v;
		// printf("%d %d\n",l,r);
	}
	printf("%d",res);
	return 0 ;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
using namespace std;
 
typedef   long long int ll;
typedef unsigned long long int sll;
typedef  double ld;
#define A 1000000007ll
#define B 998244353ll
#define C 1000000000000000001ll
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define oset tree<pair<ll,ll>, null_type,less<pair<ll,ll>>, rb_tree_tag,tree_order_statistics_node_update> 
#define pb push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define mxe(v) *max_element(v.begin(),v.end())
#define mne(v) *min_element(v.begin(),v.end())
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define ve vector
#define br break
#define PI 3.14159265358979323

int main() 
{
    FAST;
    ll n;
    cin>>n;
    ll a[n],b[n+1],c[n];
    for(int i=0;i<n;i++)
    	cin>>a[i];
    for(int i=0;i<n;i++)
    	cin>>b[i+1];
    for(int i=1;i<n;i++)
    	cin>>c[i];
    ll ans=0;
    for(int i=0;i<n;i++)
    {
    	ans+=b[a[i]];
    	if(i!=0 && a[i-1]==a[i]-1)
    		ans+=c[a[i]-1];
    }
    cout<<ans;
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Measured memory_bytes: 256
import math
n = int(input())
a = list()
d = dict()
for i in range(n):
    b = list(input())
    b.sort()
    moji = "".join(b)
    if (moji in d):
        d[moji] += 1
    else:
        d[moji] = 1
x = 0
for i in d:
    if d[i] >=1:
        x += d[i]*(d[i]-1)/2
print(int(x))

#非最適化ソート
# for i in range(n):
#     a.append(input())
# for i, youso in enumerate(a):
#     b = list()
#     for j in youso:
#         b.append(j)
#     b.sort()
#     x = str()
#     for j in b:
#         x += j
#         a[i] = x

#TLE ver.
# for i, youso in enumerate(a):
#     for j in range(i, n-1):
#         if youso == a[j+1]:
#             x += 1
# print(x)

#TLE改良版
# a.sort()
# for i in range(n-1):
#     if a[i] == a[i+1]:
#         for j in range(i+1, n):
#             if a[i] == a[j]:
#                 x += 1
#             else:
#                 break
#     else:
#         continue



#いらない処理
# y = 0
# for i in range(1, x+1):
#     y += i

Measured memory_bytes: 17932
import java.util.Scanner;

public class Main
{
    public static void main(String[] args) 
    {
       Scanner sc=new Scanner(System.in);
       int n=sc.nextInt();
       int cnt=-1,ans=0;
       for(int i=1; i<=n; i++ )
       {
            int temp=i;
            int cnt1=0;
            while(temp%2==0)
            {
                temp/=2;
                cnt1++;
            }
            if(cnt1>=cnt)
            {
                cnt=cnt1;
                ans=i;
            }
        }
        System.out.println(ans);         
    }

    
}

Measured memory_bytes: 35824
def read_input():
    s = input()
    return s


def submit():
    s = read_input()

    n = len(s)
    l = s[0]
    r = s[-1]

    if l == r:
        if n % 2 == 1:
            print('Second')
        else:
            print('First')
    else:
        if n % 2 == 1:
            print('First')
        else:
            print('Second')


if __name__ == '__main__':
    submit()


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

void solve(int x,int y,int z){
}

int main(){
   int a,b,c,k,sum=0;
   cin>>a>>b>>c>>k;
   if(k<=a)
        sum=k;
   else if(k>a && k<=a+b)
        sum=a;
   else
        sum=a-(k-a-b);
   cout<<sum;

}


Measured memory_bytes: 3612
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 3003;
int n;
string S[N], MX[N];
int main()
{
    cin >> n >> S[0];
    for (int i = 1; i < n; i++)
    {
        int a = 0, b = 0;
        for (int j = 0; j < (int)S[i - 1].size(); j++)
        {
            if (S[i - 1][j] == 'a') a ++;
            if (S[i - 1][j] == 'b') b ++;
            if (S[i - 1][j] == 'a' && a > 1) S[i] += 'a';
            if (S[i - 1][j] == 'b' && b > 1) S[i] += 'b';
        }
    }
    for (int i = n - 1; ~ i; i --)
    {
        int mb = -1;
        for (int j = 0; j < n + n - i - i && !~mb; j++)
            if (S[i][j] == 'b') mb = j;
        MX[i] = MX[i + 1];
        if (S[i][0] == 'a')
            MX[i] = max(MX[i], "ab" + MX[i + mb]);
        else
        {
            string str = "";
            int a = 0, b = 0;
            for (int j = 0; j < n + n - i - i; j++)
            {
                str += S[i][j];
                if (S[i][j] == 'a') a ++;
                if (S[i][j] == 'b') b ++;
                if (a == b)
                    MX[i] = max(MX[i], str + MX[i + 1 + (j >> 1)]);
            }
        }
    }
    return cout << MX[0], 0;
}

Measured memory_bytes: 28800
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include <iomanip>
#include <complex>
#include <bitset>
#include <stack>
 
using namespace std;
 
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define repl(i,s,n) for(int i=s; i<=n; ++i)
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define ktya(x) sort(all(x))
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define all(o) (o).begin(), (o).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 INF 1e18
#define INFLL 1000000000000000007LL
#define SIZE 200105
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define mind(a,b) (a>b?b:a)
#define maxd(a,b) (a>b?a:b)

typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
typedef pair<int,ll> pill; typedef pair<ll,int> plli; 
typedef pair<double, int> pdi;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
typedef complex<double> P;
ll MOD = 1000000007;
//ll MOD=998244353;
typedef ll Weight;
struct Edge {
	int src, dst;
	Weight weight;
};
bool operator < (const Edge &e, const Edge &f) {
	return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
	e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
int N,M;
vi S,T;
ll dp[2005][2005][2]={0};
int main(){
	cin>>N>>M;
	rep(i,N){
		int x;
		cin>>x;
		S.pb(x);
		
	}
	vi data[114514];
	rep(i,M){
		int x;
		cin>>x;
		T.pb(x);
		data[x].pb(i);
	}
	rep(i,M+1)dp[0][i][0]=1;
	rep(i,N+1)dp[i][0][0]=1;
	rep(i,N)rep(j,M){
		int x=i+1;
		int y=j+1;
		dp[x][y][0]=dp[x-1][y][0]+dp[x-1][y][1];
		dp[x][y][0]%=MOD;
		dp[x][y][1]=dp[x][y-1][1];
		if(S[i]==T[j]){
			dp[x][y][1]+=dp[x-1][y-1][0];
			dp[x][y][1]%=MOD;
			dp[x][y][1]+=dp[x-1][y-1][1];
			dp[x][y][1]%=MOD;
		}
	}
	cout<<(dp[N][M][0]+dp[N][M][1])%MOD<<endl;
}

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

const int DIM = 1e5 + 5;

int val[DIM];
vector<int> edg[DIM];
priority_queue<pair<int, int>> prq;

int main(void) {
    int n;
    cin >> n;
    
    fill(val + 1, val + n + 1, -1);
    
    for (int i = 2; i <= n; ++i) {
        int x, y;
        cin >> x >> y;
        
        edg[x].push_back(y);
        edg[y].push_back(x);
    }
    
    int m;
    cin >> m;
    
    for (int i = 1; i <= m; ++i) {
        int x, v;
        cin >> x >> v;
        
        val[x] = v;
        prq.push(make_pair(-v, x));
    }
    
    while (prq.size()) {
        int x = prq.top().second; prq.pop();
        
        for (int y : edg[x]) {
            if (val[y] == -1) {
                val[y] = val[x] + 1;
                prq.push(make_pair(-val[y], y));
            }
            else
            if (abs(val[x] - val[y]) != 1) {
                cout << "No\n";
                return 0;
            }
        }
    }
    
    cout << "Yes\n";
    for (int i = 1; i <= n; ++i)
        cout << val[i] << "\n";
    
    return 0;
}

Measured memory_bytes: 7924
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < n; ++i)
#define repr(i,x,n) for (int i = x; i < n; ++i)
#define INF 999999999;

int n;
int util[110000][3];
long long dp[110000][3];

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> util[i][0] >> util[i][1] >> util[i][2];

    for (int i = 1; i <= n; ++i) {
        for (int today = 0; today < 3; ++today) {
            for (int yesterday = 0; yesterday < 3; ++yesterday) {
                if (today == yesterday) {
                    continue;
                }
                dp[i][today] = max(dp[i][today], dp[i-1][yesterday] + util[i][today]);
            }
        }
    }
    long long ans = 0;
    rep(i,3) {
        ans = max(ans, dp[n][i]);
    }
    cout << ans << endl;
    return 0;
}


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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

S = input()
S = S + 'R'  # 下のループで最後の一回の加算を行う

A = [0] * len(S)

# 十分大きな(最大の連続するRかLの長さ程度<10**5)偶数回後には、RLと連続する箇所以外は全て0になる

conf = 0
even, odd = 0, 0
for i in range(len(S)-1):
    if i % 2:
        odd += 1
    else:
        even += 1

    if S[i+1] != S[i] and S[i] == 'R':
        conf = i
        if conf % 2:
            A[conf] += odd
            A[conf+1] += even
        else:
            A[conf] += even
            A[conf+1] += odd
        even, odd = 0, 0

    if S[i+1] != S[i] and S[i] == 'L':
        if conf % 2:
            A[conf] += odd
            A[conf+1] += even
        else:
            A[conf] += even
            A[conf+1] += odd
        even, odd = 0, 0


A = [str(i) for i in A[:-1]]
res = " ".join(A)
print(res)


Measured memory_bytes: 17832
#include<bits/stdc++.h>
#define repeat(i,n) for(int i=0; i<n; i++)
using namespace std;

int main(){
  string S, ans;
  cin >> S;
  
  repeat(i,3){
    if(S[i]==S[i+1]){
      ans = "Bad";
      break;
    }else{
      ans = "Good";
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#include <math.h>
#include <time.h>
using namespace std;
const long long mod = 1000000007;
#define ll long long
#define P pair<int, int>
#define dump(x)                             \
    if (dbg) {                              \
        cout << #x << " = " << (x) << endl; \
    }
bool dbg = false;
long long gcd(long long a, long long b){
   if (a % b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a % b));
   }
}
long long lcm(long long a, long long b){
   return (a / gcd(a, b))* b;
}
//---------------------------------------------------------------------------------------------------
/*ここからいじる*/
//---------------------------------------------------------------------------------------------------
int n, k;

void solve(){
}
int main(){
    int n;
    cin >> n;
    vector<int>an(n);
    vector<int>ans(n);
    for(int i = 0; i < n - 1; i++){
        cin >> an.at(i + 1);
        an.at(i + 1)--;
        ans.at(an.at(i + 1))++;
    }
    for(int i = 0; i < n; i++){
        cout << ans.at(i) << endl;
    }
    solve();
    return 0;
}



Measured memory_bytes: 4844
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] a = new int[3];
		int i;
		for(i = 0;i < 3;i ++) {
			a[i] = sc.nextInt();
		}
		Arrays.sort(a);
		String as = String.valueOf(a[2]) + String.valueOf(a[1]);
		int ai = Integer.valueOf(as);
		System.out.println(ai+a[0]);
	}
}

Measured memory_bytes: 22740
# coding:utf-8

import sys
import math
import time
import numpy as np
import collections
from collections import deque
import queue
import copy

# 最大公約数
def gcd(m,n):
  x = max(m,n)
  y = min(m,n)
  if x%y == 0:
    return y
  else:
    while x%y != 0:
      z = x%y
      x = y
      y = z
    else:
      return z

# 幅優先探索(BFS)でスタート座標(x, y)からの最大距離返す
def bfs(SS, x, y, H, W):#入力(座標系(迷路), x, y, xの端, yの端)
  x_next = [0, 0, -1, 1]
  y_next = [1, -1, 0, 0]
  tempx = x
  tempy = y
  mlength = 0
  q = deque()
  xytuple = (x, y, 0)
  q.append(xytuple)


  while q:
    xytuple = q.popleft()
    SS[xytuple[0]][xytuple[1]] = "x" #探索した場所は探索できないようにする
    for i in range(4): #このforで上下左右を調べてる
      tempx = xytuple[0] + x_next[i]
      tempy = xytuple[1] + y_next[i]
      #print(tempx, tempy, xytuple[2])
      #print(S)
      if(0 <= tempx and tempx < H and 0 <= tempy and tempy < W and SS[tempx][tempy] == "."):
        temptuple = (tempx, tempy, xytuple[2]+1)
        SS[temptuple[0]][temptuple[1]] = "x" #探索した場所は探索できないようにする
        mlength = max(mlength, xytuple[2] +1)
        q.append(temptuple)
      #print(q)
  return mlength

def brick(a,n,m,N):#ABC 148
  #n番目以降にmがあるか調べる
  if not m in a[n:]:
    print(N-(m-1))
  else:
    #b = copy.deepcopy(a)
    brick(a,a[n:].index(m),m+1,N)

#X = str(input()).split()
#a = [int(x) for x in input().split()]
#HA = str(input()).split()
H = int(input())
#A = int(HA[1])
#a = [int(x) for x in input().split()]

H_str = bin(H)

bit = len(H_str)-3

ans = 2 ** bit
ans = ans *2
ans -= 1
print(ans)


Measured memory_bytes: 12484
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define eps 1e-10

struct Point{double x,y;};
bool comp(Point a,Point b) {return (a.x==b.x ? a.y<b.y : a.x<b.x);}
double dist(Point a,Point b) {return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));}

bool Intersection(Point p1,Point p2,Point p3,Point p4,Point *ret){
    double d = (p2.x-p1.x)*(p4.y-p3.y)-(p2.y-p1.y)*(p4.x-p3.x);
    double u = ((p3.x-p1.x)*(p4.y-p3.y)-(p3.y-p1.y)*(p4.x-p3.x))/d;
    double v = ((p3.x-p1.x)*(p2.y-p1.y)-(p3.y-p1.y)*(p2.x-p1.x))/d;
    if(d==0 || u<=0 || u>=1 || v<=0 || v>=1)return false;
    ret->x = p1.x+u*(p2.x-p1.x);
    ret->y = p1.y+u*(p2.y-p1.y);
    return true;
}

int main(void){
    int n;
    while(cin>>n,n){
    	int division=1;
        vector<Point> p1(n);
        vector<Point> p2(n);
    	rep(i,n){
            cin>>p1[i].x>>p1[i].y>>p2[i].x>>p2[i].y;
            vector<Point> cross;
            rep(j,i){
                Point ret;
                if(Intersection(p1[i],p2[i],p1[j],p2[j],&ret)){
                    cross.push_back(ret);
                }
            }
            sort(cross.begin(),cross.end(),comp);
            int cnt=1;
            if(cross.size()==0)cnt=0;
            for(int j=0;j+1<cross.size();j++){
                cnt+=(dist(cross[j],cross[j+1])>=eps);
            }
            division += cnt+1;
        }
        cout<<division<<endl;
    }

    return 0;
}

Measured memory_bytes: 1260
N,K = map(int,input().split()) #intでインプット
li=[]
d=[]
counter=[0]*N
for i in range(K):
    d.append(input())
    li.append(list(map(int,input().split())))
    for j in li[i]:
        counter[j-1]+=1
print(len([i for i, x in enumerate(counter) if x == 0]))

Measured memory_bytes: 9148
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cmath>
#define rep(i,cc,n) for(int i=cc;i<=n;++i)
#define drep(i,cc,n) for(int i=cc;i>=n;--i)
typedef long long ll;
using namespace std;
int main(){
    int x,y,z;
    cin>>x>>y>>z;
    int ans=0;
    x = x - 2*z;
    if(x>=y){
        x = x - y;
        //ans++;
        while(1){
            if(x>=0){
                ans++;
                x = x - (y+z);
            }
            else break;
        }
    } 
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
# list(map(int, input().split()))

n = int(input())
A = list(map(int, input().split()))
q = int(input())

count = [0] * (10 ** 5 + 1)

total = 0
for a in A:
    count[a] += 1
    total += a

for i in range(q):
    b, c = map(int, input().split())
    nums = count[b]
    total += (c - b) * nums
    count[b] = 0
    count[c] += nums
    print(total)


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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    stack<char> ans;
    for (int i = 0; i < s.size(); i++) {
        if (ans.empty()) {
            ans.push(s[i]);
        } else if (ans.top() == 'S' && s[i] == 'T') {
            ans.pop();
        } else {
            ans.push(s[i]);
        }
    }
    cout << ans.size() << endl;
    return 0;
}

Measured memory_bytes: 720
#include <iostream>
using namespace std;
 
int main() {
	while(1){
		int l;
		cin>>l;
		if(l==0){break;}
		int a=0;
		int i =1;
		int ans=1;
		while(i<=12){
			int p,o;
			cin>>p>>o;
			a=a+p-o;
			if(a<l){ans++;}
			i++;
		}
		if(a>=l){cout<<ans<<endl;}
		else{cout<<"NA"<<endl;}
	}
	return 0;
}

Measured memory_bytes: 1164
//abc071_a.cpp
//Sun Sep 30 15:50:08 2018

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

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

	if (abs(x-a) > abs(x-b)){
		cout << "B" << endl;
	}else{
		cout << "A" << endl;
	}
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
        
    	int x = sc.nextInt();
    	int y = sc.nextInt();
    	int j=1,z;
    	while(j<=x||j<=y){
    		if(x>=y){
    			z=x;
    			x=y;
    			y=z;
    		}
    		 System.out.println(x+" "+y);
    	   x = sc.nextInt();
    	   y = sc.nextInt();
    		}
 
    	
        sc.close();
}
}



Measured memory_bytes: 36068
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

r  = INT()
# s = r * r * Math.pi
# s1  = 1 * 1 * 
print(r * r)
# a, b = MAP()
# print(a, b)


Measured memory_bytes: 5144
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <queue>
#include <stack>
// auto は　-std=c++11つける
using namespace std;

int main(){

  long N,M;
  long a[200005],b[200005],c[200005];
  vector<long> path,path2;
  vector<long> sum;
  bool clear = false;
  fill_n(c,200005,0);
  cin >> N >> M;

  for(long i=0;i<M;++i){
    cin >> a[i] >> b[i];
    if(a[i]==1){
      c[b[i]] = 1;
    }else if(b[i]==1){
      c[a[i]] = 1;
    }
  }

  for(long i=0;i<M;++i){
    if(a[i]==N && c[b[i]]==1){
      clear = true;
      break;
    }else if(b[i]==N&&c[a[i]]==1){
      clear = true;
      break;
    }
  }

  if(clear){
    cout << "POSSIBLE" << endl;
  }else{
    cout << "IMPOSSIBLE" << endl;
  }
  return 0;
}

Measured memory_bytes: 4992
import collections
n = int(input())
a = list(map(int,input().split()))
c = sorted(collections.Counter(a).items(),reverse = True)

num2 = []
num4 = []
ans = [0]

for k in c:
  if k[1]>=4:
    num4.append(k[0])
  if k[1]>=2:
    num2.append(k[0])

if len(num2)>=2:
  ans.append(num2[0]*num2[1])
if len(num4)>=1:
  ans.append(num4[0]**2)

print(max(ans))

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

using lint = long long;
const lint MOD = 1e9 + 7;

lint minv(lint n) {
    lint res = 1, power = MOD - 2;
    while (power > 0) {
        if (power%2 == 1) {
            res = (n*res)%MOD;
        }
        n = (n*n)%MOD;
        power /= 2;
    }

    return res;
}

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

    int N;
    lint X;
    cin >> N >> X;
    vector<lint> S(N);
    for (int i = 0; i < N; i++) {
        cin >> S[i];
    }
    sort(S.begin(), S.end(), greater<lint>());

    vector<vector<lint>> dp(N + 1, vector<lint>(X + 1, 0));
    for (int x = 0; x <= X; x++) {
        dp[N][x] = x;
    }

    for (int i = N - 1; i >= 0; i--) {
        lint inv = minv(N - i);
        for (int x = 0; x <= X; x++) {
            dp[i][x] = (dp[i + 1][x]*(N - i - 1)%MOD + dp[i + 1][x%S[i]]%MOD)*inv%MOD;
        }
    }

    for (int n = 1; n <= N; n++) {
        dp[0][X] = (dp[0][X]*n)%MOD;
    }

    cout << dp[0][X] << endl;
    return 0;
}

Measured memory_bytes: 158592
#include <bits/stdc++.h>
/**
AHMAD;HASSAN;SAEED
*/
using namespace std;

int main()
{
    string b;
    long long a;
    cin>>a>>b;
    b.erase(1,1);
    while(b.length()<3)
        b+='0';
    istringstream iss(b);

    long long nb;
    iss>>nb;
    long long ans=a*nb;
    ans/=100ll;

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


Measured memory_bytes: 3504
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
const int MAX = 5000;
const int MOD = 1000000007;
 
ll fac[MAX], finv[MAX], inv[MAX];
 
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
 
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
 
int main(){
    ll n, k;
    cin >> n >> k;
    COMinit();
    for (int i = 1; i <= k; i++) {
        cout << (COM(n - k + 1, i) * COM(k - 1, k - i)) % MOD << endl;
    }
}

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

#define fs first
#define sc second

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; }


// 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::multiset Debug
template<typename T>
ostream& operator<<(ostream& os, const multiset<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) cerr<<#x<<" = "<<(x)<<endl


struct edge { int to, cost; };
ostream& operator<<(ostream& os, const edge& e) {
    os << "(" << e.to << ", " << e.cost << ")";
    return os;
}

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

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

    int m = 2*d + 1;

    int ans = n / m + (n % m != 0);

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
n, m = map(int, input().split())
a = [input() for _ in range(n)]
b = [input() for _ in range(m)]

success = 0
for i in range(n - m + 1):
    fail = 0
    for j in range(n - m + 1):
        fail = 0
        for ii in range(m):
            for jj in range(m):
                if b[ii][jj] == a[i + ii][j + jj]:
                    continue
                else:
                    fail = 1
                    break
            if fail == 1:
                break
        else:
            success = 1
            print('Yes')
            break
    if success == 1:
        break
else:
    if fail == 1:
        print('No')

Measured memory_bytes: 9144
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[] hav = new int[M];
		for(int i=0;i<N;i++) {
			int K = sc.nextInt();
			for(int j=0;j<K;j++) {
				hav[sc.nextInt()-1]++;
			}
		}
		int count = 0;
		for(int i=0;i<M;i++) {
			if(hav[i]==N) count++;
		}
		System.out.println(count);
	}
}

Measured memory_bytes: 24660
#関数リスト
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

x,n = MI()
mylist = tuple(MI())

num = 0
while True:
    if not(x - num in mylist):
        print(x- num)
        sys.exit()
    if not(x + num in mylist):
        print(x+ num)
        sys.exit()
    num += 1

Measured memory_bytes: 62024
#include<bits/stdc++.h>
    using namespace std;
  #define int long long int
    #define endl "\n"
    #define MOD 1000000007
    #define mod 1000000007
    #define M 1000000007
    
    #define pb push_back
    #define take(a,b,c) for(int b=0;b<c;b++) cin>>a[b]
  //  #define mp make_pair
  #define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
  #define mx 400005
  #define fiint(a,b) memset(a,b,sizeof(a))  
  #define bitcount __builtin_popcount
  #define fori(i,a,b) for(int i=a;i<b;i++)
  #define ford(i,a,b) for(int i=a;i>=b;i--)
  #define debug(x) cout<<x<<endl;
  #define cases(t) int t; cin>>t; while(t--)
  #define inf1 INT_MAX
  #define all(a) a.begin(),a.end()
  #define vec vector<int>
  #define pii pair<int,int>
  #define plii pair<int,int>
  #define pint pair<int,int>
  #define ff first
  #define ss second
  #define lb lower_bound
  #define ub upper_bound
  #define bs binary_search
  #define sz(x) (int)x.size()
#define PI                    3.14159265359

bool prime[10000001];

void sieveFunction(int maxLimit){
    memset(prime, true, sizeof(prime));
    prime[0] = prime[1]=false;
    for(int i=2; maxLimit >= i ; i++){
        if(prime[i]){
            for(int j=2*i ; maxLimit >= j ; j+=i)
                prime[j]=false;
        }
    }
}

void add_self(int& a, int b) {
    a += b;
    if(a >= mod) {
        a -= mod;
    }
}

void sub_self(int& a, int b) {
    a -= b;
    if(a < 0) {
        a += mod;
    }
}

vec adj[mx];

int mul(int a, int b) {
    return (int) a * b % mod;
}

pair<int,int> dfs(int v,int p )
{
	int all_white =1 ;
	int some_black = 0 ; 
	for(auto it : adj[v])
	{
		if(it != p)
		{
			pair<int,int> bw = dfs(it, v);
			int temp_all_white = all_white;
			all_white = mul(all_white , bw.ss);
			some_black = (mul(temp_all_white , bw.ff  ) + mul(some_black , bw.ff + bw.ss ))%mod;
		}

	}
	return { all_white , (all_white  + some_black)%mod };
}



signed  main() 
{ 
	int n;cin>>n;
	fori(i,1,n)
	{
		int u,v;cin>>u>>v;
		adj[u].pb(v);
		adj[v].pb(u);
	}

	pair<int,int> temp = dfs(1,-1);
	int ans= temp.ff + temp.ss ; 
	cout<<ans%mod<<endl;

}

 


Measured memory_bytes: 20608
#include<iostream>
#include<iomanip>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<string>
#include<algorithm>
#include<functional>
#include<math.h>
#include<unordered_set>
using namespace std;
const long long L_INF = 9223372036854775807;
const int INF = 10000;
const int MAX = 50;

int match(string s, string t) {
	for (int i = s.length() - t.length(); i >= 0; i--) {
		for (int j = 0; j < t.length(); j++) {
			if (s[i + j] != t[j] && s[i + j] != '?')break;
			if (j == t.length() - 1)return i;
		}
	}
	return -1;
}

int main() {
	string s, t;
	bool flag = false;

	cin >> s >> t;

	int pos = match(s, t);

	if (pos != -1) {
		for (int i = 0; i < t.length(); i++) {
			s[pos + i] = t[i];
		}
		for (int i = 0; i < s.length(); i++) {
			if (s[i] == '?')s[i] = 'a';
		}

		cout << s << endl;
	}
	else {
		cout << "UNRESTORABLE" << endl;
	}
	
	return 0;
}

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

int main(){
	int a, b, c;
	cin >> a >> b >> c;
	if(a+b >= c){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}
	return 0;
}

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

using namespace std;

int main()
{
    string s , t; cin>>s>>t;
    bool ok = 1;
    for(int i = 0 ; i < s.size(); ++i){
        if(s[i] == t[i])ok &= 1;
        else ok &= 0;
    }
    if(t.size() <= s.size())cout<<"No";
    else if(!ok || t.size() - s.size() > 1)cout<<"No";
    else cout<<"Yes";
   return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define rep(i,n) for (int (i) = 0; (i) < (n); i++)
#define ll long long
using namespace std;
int main() {
  ll N = 0,ans = 0;
  cin >> N;
  vector<ll>A(N);
  rep(i,N){
    cin >> A[i];
  }
  for(ll i = 0;i < N-1;i++){
    for(ll j = 1;j + i < N;j++){
      ans+=A[i] * A[i+j];
    }
  }
  cout << ans;
}
  

Measured memory_bytes: 3604
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }
    public void solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 3; i++) {
            String s = scan.next();
            sb.append(s.toCharArray()[i]);
        }
        System.out.println(sb.toString());
    }
}


Measured memory_bytes: 21844
#include<iostream>
#include<string>

using namespace std;
int main(){
	while(1){
	string r;
	cin>>r;
	if(r=="-")break;
	int num=r.size();
	//cout<<num<<endl;
	int n,c;
	cin>>n;
	for(int i=0;i<n;i++){
		r=r+r;
		//cout<<r<<endl;
		cin>>c;
		r=r.substr(c,num-c+1*c);
		//cout<<r<<endl;
	}
	cout<<r<<endl;
	}
	return 0;
}


Measured memory_bytes: 3172
n=int(input())
l=[]

for i in range(n):
  a=int(input())
  l.append(a)
  
l.sort(reverse=True)

ans=1
for i in range(0,n-1):
  if l[i]==l[i+1]:
    continue
  else:
    ans+=1
print(ans)

Measured memory_bytes: 3064
# A - Sorted Arrays
import numpy as np

N = int(input())
A = list(map(int, input().split()))
sgn = 0
ans = 1

for i in range(N-1):
    tmp = np.sign(A[i+1]-A[i])
    if tmp*sgn<0:
        ans += 1
        sgn = 0
    else:
        sgn = np.sign(2*sgn+tmp)

print(ans)

Measured memory_bytes: 23208
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
ll k,a,dp[2<<17],m=1e9+7;
int i,n,j;
main(){
	cin>>n>>k;
	dp[0]=1;
	for(i=0;i<n;i++){
		cin>>a;
		for(j=1;j<=k;j++)dp[j]+=dp[j-1];
		for(j=k;j>=1;j--) 
		{if(j-a-1>=0) dp[j]=(dp[j]-dp[j-a-1])%m;
		else dp[j]%=m;}
	}
	cout<<dp[k];
}

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

#define pb push_back
#define sz size()
#define clr clear()
#define M 999983

vector<bool> pt;
vector<int> pa;

void MakeTable(int n){
  pt.clr;
  pt.pb(false);pt.pb(false);pt.pb(true);
  
  while((int)pt.sz<=n+1){
    pt.pb(true);
    pt.pb(false);
  }
  
  int i = 3;
  while(i*i<=n){
    for(int j=3*i;j<=n;j+=2*i)pt[j]=false;
    do{i+=2;}while(!pt[i]);
  }
}

int main(){
  int n,p,m,pn[1000000];
  long long ans;

  MakeTable(M);
  int cnt = 0;
  for(int i=0;i<=M;i++){
    if(pt[i])cnt++;
    pn[i] = cnt;
  }

  for(;;){
    cin >> n;
    if(!n)break;

    ans = 0;
    for(int i=0;i<n;i++){
      cin >> p >> m;
      int l = max(0,p-m-1),r = min(M,p+m);

      if(pn[r]-pn[l]>0)ans += pn[r] - pn[l] - 1;
      else ans--;
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 0
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl;
#define debug2(x, y) debug(x) debug(y);
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))

template<class T> T gcd(T a, T b){ return ((b == 0) ? a : gcd(b, a % b)); }

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	int n, z, w;
	cin >> n >> z >> w;
	vi a(n);
	rep(i, n) cin >> a[i];
	if(n == 1) cout << abs(a[0] - w) << endl;
	else cout << max(abs(a[n - 1] - w), abs(a[n - 2] - a[n - 1])) << endl;
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/


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

using Int = long long;
const char newl = '\n';

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}
template<typename T=int>
vector<T> read(size_t n){
  vector<T> ts(n);
  for(size_t i=0;i<n;i++) cin>>ts[i];
  return ts;
}


template<typename T,T MOD = 1000000007>
struct Mint{
  static constexpr T mod = MOD;
  T v;
  Mint():v(0){}
  Mint(signed v):v(v){}
  Mint(long long t){v=t%MOD;if(v<0) v+=MOD;}

  Mint pow(long long k){
    Mint res(1),tmp(v);
    while(k){
      if(k&1) res*=tmp;
      tmp*=tmp;
      k>>=1;
    }
    return res;
  }

  static Mint add_identity(){return Mint(0);}
  static Mint mul_identity(){return Mint(1);}

  Mint inv(){return pow(MOD-2);}

  Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;}
  Mint& operator/=(Mint a){return (*this)*=a.inv();}

  Mint operator+(Mint a) const{return Mint(v)+=a;}
  Mint operator-(Mint a) const{return Mint(v)-=a;}
  Mint operator*(Mint a) const{return Mint(v)*=a;}
  Mint operator/(Mint a) const{return Mint(v)/=a;}

  Mint operator-() const{return v?Mint(MOD-v):Mint(v);}

  bool operator==(const Mint a)const{return v==a.v;}
  bool operator!=(const Mint a)const{return v!=a.v;}
  bool operator <(const Mint a)const{return v <a.v;}

  static Mint comb(long long n,int k){
    Mint num(1),dom(1);
    for(int i=0;i<k;i++){
      num*=Mint(n-i);
      dom*=Mint(i+1);
    }
    return num/dom;
  }
};
template<typename T,T MOD> constexpr T Mint<T, MOD>::mod;
template<typename T,T MOD>
ostream& operator<<(ostream &os,Mint<T, MOD> m){os<<m.v;return os;}

//INSERT ABOVE HERE
const int MAX = 3030;
using M = Mint<int, 998244353>;
M dp[MAX][MAX]={};

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  dp[a][b]=1;

  for(int i=a;i<=c;i++){
    for(int j=b;j<=d;j++){
      if(i==a and j==b) continue;
      dp[i][j]+=dp[i-1][j-0]*M(j);
      dp[i][j]+=dp[i-0][j-1]*M(i);
      dp[i][j]-=dp[i-1][j-1]*M(i-1)*M(j-1);
    }
  }

  cout<<dp[c][d]<<endl;
  return 0;
}


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

using ll = long long;
using P = pair<ll, ll>;

const ll MOD = 1e9+7;
// const ll MOD = 998244353;
const ll INF = 1ll<<60;

#define FOR(i,a,b) for (ll i=(a);i<(ll)(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define DEBUG(x) std::cerr << #x << " : " << (x) << std::endl;

int main(int argc, char **argv)
{
	ll N, M; cin >> N >> M;
	vector<vector<ll>> G(N);
	vector<ll> deg(N, 0);
	REP(i, N-1+M)
	{
		ll a, b; cin >> a >> b;
		--a, --b;
		G[a].push_back(b);
		++deg[b];
	}

	queue<ll> que;
	REP(i, N) if (!deg[i]) que.push(i);

	vector<ll> res;
	vector<ll> par(N, 0);
	while (que.size())
	{
		ll v = que.front();
		que.pop();
		res.push_back(v);
		for (auto &nv : G[v])
		{
			--deg[nv];
			if (!deg[nv])
			{
				par[nv] = v + 1;
				que.push(nv);
			}
		}
	}

	for (ll i = 0; i < N; ++i)
		std::cout << par[i] << std::endl;
}


Measured memory_bytes: 8820
#include <bits/stdc++.h>
using namespace std;
int main(){
  int a;
  int b;
  int c;
  int d;
  int e;
  int f;
  cin>>a>>b>>c>>d;
  e=0;
  f=0;  
  
    while(b<=a){
      b=2*b;
      
      e+=1;
    }
  
  
  
    while(c<=b){
      c=2*c;
      f+=1;
    }
  
  
  
  if(e+f<=d){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
}
  

Measured memory_bytes: 3632
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author aajisaka
 */

#include<bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SPEED ios_base::sync_with_stdio(false);cin.tie(nullptr)
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;

constexpr long double PI = 3.14159265358979323846264338327950288L;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

class UGrouping {
public:
    void solve(istream& cin, ostream& cout) {
      SPEED;
      int n; cin >> n;
      vector<vector<ll>> a(n, vector<ll>(n));
      rep(i, n) rep(j, n) {
        cin >> a[i][j];
      }
      int s = 1<<n;
      vector<ll> dp(s);
      rep(i, s) {
        vector<int> rabbits;
        rep(k, n) {
          if (i&(1<<k)) {
            rabbits.push_back(k);
          }
        }
        for(auto e: rabbits) {
          for(auto f: rabbits) {
            dp[i] += a[e][f];
          }
        }
        dp[i]/=2;
        chmax(dp[i], 0LL);
        //debug(i, dp[i]);
      }

      rep(i, s) {
        for(int j=(i-1)&i; j>0; j=(j-1)&i) {
          chmax(dp[i], dp[j] + dp[i^j]);
        }
        //debug(i, dp[i]);
      }

      cout << dp[s-1] << endl;
    }
};

signed main() {
  UGrouping solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+7;
int dp[N][3];
int main()
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	int n;
	cin >> n;
	int ara[n][3];	
	for(int i = 0;i<n;i++)
		cin >>ara[i][0] >>ara[i][1] >>ara[i][2];
	dp[0][0] = ara[0][0];
	dp[0][1] = ara[0][1];
	dp[0][2] = ara[0][2];
	for(int i = 1;i<n;i++) {
		for(int j = 0;j<3;j++) {
			if(j==0) dp[i][0] = ara[i][0]+max(dp[i-1][1],dp[i-1][2]);
			else if(j==1)dp[i][1]  =  ara[i][1]+max(dp[i-1][0],dp[i-1][2]);
			else dp[i][2] =  ara[i][2]+max(dp[i-1][0],dp[i-1][1]);
		}
	}
	cout <<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));
	return 0;
}

Measured memory_bytes: 5900
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
struct Edge{
	int to,nxt;
	bool flag;
}edge[200100];
struct Point{
	int color,cnt,vis,size,depth,cnt2;
}point[200100];
int head[200100],flag[200100],n,m,X,Y,cnt=1,bo,x,y;
void dfs2(int x){
	point[x].cnt2=point[x].color,flag[x]=1;
	for (int i=head[x];i;i=edge[i].nxt){
		int upup=edge[i].to;
		if(!flag[upup]&&!edge[i].flag){
			dfs2(upup);
			point[x].cnt2+=point[upup].cnt2;
		}
	}
}
int solve(){
	memset(flag,0,sizeof flag);
	dfs2(1);
	int ans=0;
	for(int i=1;i<=n;i++)
		ans+=abs(point[i].size-point[i].cnt-point[i].cnt2);
	return ans;
}
int check(int x){
	point[X].color-=x;point[Y].color+=x;
	int k=solve();
	point[X].color+=x;point[Y].color-=x;
	return k+abs(x);
}
void addedge(int x,int y){
	edge[++cnt].to=y;
	edge[cnt].nxt=head[x];
	head[x]=cnt;
	edge[cnt].flag=0;
}
void dfs(int x,int fa){
	point[x].color=1-point[fa].color;
	point[x].cnt=point[x].color;
	point[x].vis=1;
	point[x].size=1;
	point[x].depth=point[fa].depth+1;
	for(int i=head[x];i;i=edge[i].nxt){
		int upup=edge[i].to;
		if(upup==fa)continue;
		if(point[upup].vis&&point[upup].depth<point[x].depth){
			X=x,Y=upup;
			bo=(point[X].depth-point[Y].depth)%2;
			edge[i].flag=edge[i^1].flag=1;
		}
		if(point[upup].vis)continue;
		dfs(upup,x);
		point[x].size+=point[upup].size;
		point[x].cnt+=point[upup].cnt;
	}
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%lld%lld",&x,&y);
		addedge(x,y);
		addedge(y,x);
	}
	point[1].color=1;
	dfs(1,0);
	int S=point[1].cnt,T=n-point[1].cnt;
	if(n==m+1){
		if(S!=T)return puts("-1"),0;
		printf("%lld\n",solve());
		return 0; 
	}
	if(bo){
		if(S!=T)return puts("-1"),0;
		int L=-n,R=n;
		while(L<=R-5){
			int mid1=L+(R-L)/3,mid2=R-(R-L)/3;
			if (check(mid1)>check(mid2))L=mid1;
			else R=mid2;			
		}
		int ans=0x3f3f3f3f3f3f3f3f;
		for(int i=L;i<=R;i++)
			ans=std::min(ans,check(i));
		printf("%lld\n",ans);
		return 0;
	}
	else{
		if((S-T)%2!=0)return puts("-1"),0;
		point[X].color+=(T-S)/2;
		point[Y].color+=(T-S)/2;
		printf("%lld\n",solve()+abs(T-S)/2);
		return 0;		
	}
}

Measured memory_bytes: 17920