akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>

using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype
template <class T> int __builtin_popcount(T n) { return n ? 1 + __builtin_popcount(n & (n - 1)) : 0; }
#endif

#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define popcount __builtin_popcount

#define rep(i, n) for (int i = 0; i < n; ++i)

template <class T> void max_swap(T& a, const T& b) { a = max(a, b); }
template <class T> void min_swap(T& a, const T& b) { a = min(a, b); }

const double EPS = 1e-10;
typedef long long ll;
typedef pair<int, int> pint;


int main()
{
	int w, q;
	while (cin >> w >> q, w | q)
	{
		int p[256];
		fill(p, p + w, -1);
		p[w] = -2;
		while (q--)
		{
			char c;
			cin >> c;
			if (c == 's')
			{
				int id, width;
				cin >> id >> width;
				int i;
				for (i = 0; i < w; ++i)
					if (count(p + i, p + i + width, -1) == width)
						break;
				if (i != w)
				{
					fill(p + i, p + i + width, id);
					cout << i << endl;
				}
				else
					cout << "impossible" << endl;
			}
			else
			{
				int id;
				cin >> id;
				replace(p, p + w, id, -1);
			}

			getchar();
		}
		cout << "END" << endl;
	}
}

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

#define rep(i, n) for(int i = 0; i < (n); ++i)

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

const int MAX = 2005;
const int INF = 1e9;
const int MOD = 1e9 + 7;

int N, K, A[MAX];

int main(){
    cin >> N >> K;
    rep(i, N) cin >> A[i];

    ll a = 0;
    rep(i, N){
        rep(j, i){
            if(A[j] > A[i]) a++;
        }
    }

    a *= K;
    a %= MOD;

    sort(A, A + N, greater<int>());

    ll b = 0;
    rep(i, N){
        rep(j, i){
            if(A[j] > A[i]){
                b++;
            }
        }
    }

    ll Kl = (ll)K * (K - 1) / 2;
    Kl %= MOD;
    b = (ll)b * Kl;
    b %= MOD;

    ll ans = a + b;
    ans %= MOD;

    cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.*;

class Main  {
  public static void main(String[] args) {

    Scanner scanner = new Scanner(System.in);
    int s = scanner.nextInt();

    int h = s/3600;
    s = s%3600;
    int m = s/60;
    s = s% 60;

    System.out.printf("%d:%d:%d\n" , h , m , s);
  }
}

Measured memory_bytes: 26480
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    static Map<String, Integer> m = new HashMap<>();
    static {
        m.put("SUN", 7);
        m.put("MON", 6);
        m.put("TUE", 5);
        m.put("WED", 4);
        m.put("THU", 3);
        m.put("FRI", 2);
        m.put("SAT", 1);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();

        System.out.println(m.get(s));
    }
}


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

const long long N = 1e3 + 17;
ll cnt, ans, lnt = N, sum, n, l1, b[N][N], a[N], x, y, mx = N;
pair<ll,ll>pr[N];
vector<ll>v,v2,v3;
map<ll,ll>mp;
bool used[N], t1, t2;
vector<string>sv;

int main()
{
    cin >> n >> x;
    for(ll i = 0; i < n; i ++)
    {
        cin >> pr[i].first >> pr[i].second;
        if(pr[i].second <= x)
        {
            mx = min(mx, pr[i].first);
        }
    }
    if(mx == N)
    {
        cout << "TLE";
    }
    else
    {
        cout << mx;
    }
}


Measured memory_bytes: 256
k,n = map(int,input().split())
a = [int(x) for x in input().split()]
dist=[]
for i in range(1,n):
    dist.append(a[i] - a[i-1])

d= k - a[-1] + a[0] # dist btw last and 1st
dist.append(d)
dist.sort()
print(sum(dist[:-1]))



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

using namespace std;
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
#define REP(i,n) for(ll i = 0;i < (ll)n;i++)
#define REPD(i,n) for(ll i = (ll)n - 1;i >= 0;i--)
#define ALL(x) (x).begin(),(x).end()
#define FILLl(n,first_dimension_size,value) fill((ll*)n,(ll*)(n+first_dimension_size),value)
#define FILL(n,first_dimension_size,value) fill((int*)n,(int*)(n+first_dimension_size),value)
#define INF (1 << 29)
#define MOD 1000000007
//int dy[4] = {-1,0,0,1};
//int dx[4] = {0,1,-1,0};

ll dp[100][100100];
const int inf = (1 << 30);

int main(){

  ll n,W;
  cin >> n >> W;
  vector<ll> w(n),v(n);
  REP(i,n)cin >> w[i] >> v[i];
  FILLl(dp,100,inf);
  dp[0][v[0]] = w[0];
  REP(i,n)dp[i][0] = 0;
  for(int i = 1;i < n;i++){
    REP(j,100001){
      if(j >= v[i])dp[i][j] = min({dp[i][j],dp[i-1][j-v[i]]+w[i],dp[i-1][j]});
      else dp[i][j] = min(dp[i-1][j],dp[i][j]);
    }
  }
  int res;
  REPD(i,100001){
    if(dp[n-1][i] <= W){
      res = i;
      break;
    }
  }
  cout << res << endl;


  

  return 0;
}


Measured memory_bytes: 78464
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef string str;
const long long INF = INT64_MAX;

#define REP(i, n) for(ll i=0;i<n;i++)
#define ASC(v) sort((v).begin(), (v).end())
#define DESC(v) sort((v).rbegin(), (v).rend())
#define UNIQ(v) ASC(v);erase(unique(v.begin(), v.end()), v.end())
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);

void solve() {
    ll a,b,c;
    cin >> a >> b >> c;
    if((a < c && c < b) || (b < c && c < a)) {
        cout << "Yes" << endl;
    }else {
        cout << "No" << endl;
    }
}

int main() {
    FIO;
    solve();
    return 0;
}

Measured memory_bytes: 256
n = int(input())
nums = list(map(int, input().split()))

bs = nums.copy()
res = []

for i in range(n // 2, 0, -1):
    val = 0
    for j in range(1, n // i + 1):
        if i * j <= n:
            val += bs[i * j - 1]
    bs[i - 1] = val % 2
for i in range(n):
    if bs[i] > 0:
        res.append(i + 1)
m = sum(bs)
print(m)
if m > 0:
    print(' '.join(map(str, res)))

Measured memory_bytes: 19892
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, x=0,count=0; cin >> n;
  vector<int> l(n);
  for(int i=0;i<n;i++) {
    cin >> l[i];
    x=max(x,l[i]);
    count+=l[i];
  }
  if(x<count-x){
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
  return 0;
}
  

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

using namespace std;

int main()
{
   int n;
   cin>>n;
   double k=(double)n/1000;
   if(n<1000)
   
   cout<<1000-n<<endl;
  else cout<<(1000*ceil(k))-n<<endl;
   
   return 0;
}

Measured memory_bytes: 3816
#include<bits/stdc++.h>
using namespace std;
int main()
{
     long long t,i,j,n,l,m,k,p;
    cin>>l;
   string s;
   cin>>s;
   n=s.length();
   if(n>l)
   {
       for(i=0;i<l;i++)
       cout<<s[i];
      cout<<"."<<"."<<".";   
   }
   else 
   cout<<s;
   
    
    
}

Measured memory_bytes: 3496
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
       
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int[] array = new int[a];
        double sum = 0;
        double ans = 0;
        for(int i = 0; i < a; i++){
            array[i] = sc.nextInt();
            sum = sum + (double)1 / array[i];
        }
        ans = 1 / sum;
        System.out.println(ans);
    }
}

Measured memory_bytes: 21844
n=int(input())
lim=len(str(n))
cand=[3,5,7]
ans=[]
while cand:
    i=cand.pop()
    for j in [3,5,7]:
        k=int(str(i)+str(j))
        if k<=n:
            cand.append(k)
            if len(set(str(k)))==3:
                ans.append(k)
print(len(ans))

Measured memory_bytes: 74140
#!/usr/bin/perl
my ($n,$t) = map { $_ - 0 } split(/\s+/,<STDIN>);
my @ct=();
for(my $i=0;$i<$n;$i++){
  my @a = map { $_ - 0 } split(/\s+/,<STDIN>);
  push(@ct,\@a);
}

my @r = grep {$_->[1]<=$t} sort { $a->[0] <=> $b->[0] } @ct;
if(@r){
  print "$r[0]->[0]\n";
} else {
  print "TLE\n";
}


Measured memory_bytes: 512
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define IO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
const int N = 2e5 + 5, M = 2 * N + 5;


int main(){
    IO;
    ll n;
    cin >> n;
    ll mn = LLONG_MAX;
    for(ll i = 1 ; i * i <= n ; ++i)
        if(n % i == 0)
            mn = min(mn, (i + n / i - 2));
    cout << mn << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
long double r;
int main() {
	while(cin >> r, r != 0.0L) {
		for(int i = 1; ; i++) {
			long double x = (3.14159265358979L * i - (int)(3.14159265358979L * i)) / i;
			long double y = ((int)(3.14159265358979L * i) - 3.14159265358979L * i + 1) / i;
			if(x <= r) {
				cout << (int)(3.14159265358979L * i) << '/' << i << endl; break;
			}
			if(y <= r) {
				cout << (int)(3.14159265358979L * i) + 1 << '/' << i << endl; break;
			}
		}
	}
}

Measured memory_bytes: 3160
#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char* argv[])
{
    int N; cin >> N;

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

    int cnt = 0;
    bool isFound = false;
    vector<bool> isArr(N, false); isArr[0] = true;
    int pos = 0;
    while (1) {
      cnt++;
        pos = A[pos];
        if (isArr[pos]) {
            break;
        } else if (pos == 1) {
            isFound = true;
            break;
        }
	isArr[pos] = true;
    }

    cout << (isFound ? cnt : -1) << endl;
    return 0;
}


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

int connectedCount(int node, vector<set<int>>& graph, vector<int>& visited)
{
	if(visited[node])
		return 0;

	int ret = 1;
	visited[node] = 1;

	for(auto& child: graph[node])
	{
		if(visited[child] == 0)
				ret += connectedCount(child, graph, visited);
	}

	return ret;
}

int main()
{
	int n, m;
 	cin >> n >> m;
	vector<set<int>> v(n+1, set<int>());
	for(int i = 0; i < m; ++i)
	{
		int a,b;
		cin >> a >> b;
		v[a].insert(b);
		v[b].insert(a);
	}
	vector<int> visited(n+1, 0);
	if(connectedCount(1, v, visited) != n)
	{
		cout << "No";
	}
	else
	{
		vector<int> parent(n+1, 0);
		vector<int> visited(n+1, 0);
		queue<int> q;
		q.push(1);
		visited[1] = 1;

		while(!q.empty())
		{
			int cnt = q.size();
			while(cnt--)
			{
			int top = q.front(); q.pop();
			for(auto& child: v[top])
			{
				if(visited[child] == 0)
				{
					visited[child] = 1;
					q.push(child);
					parent[child] = top;
				}
			}
			}
		}
		cout << "Yes\n";
		for(int i = 2; i <= n; ++i)
		{
			cout << parent[i] << "\n";
		}

		return 0;
	}
}

Measured memory_bytes: 32316
import collections

n = int(input())
a = [int(i) for i in input().split()]

if a[0] != 0:
    print(0)
    exit()

a.sort()

c = collections.Counter(a)

ans = 1
now = 1
if a[0] != 0 or a[1]==0:
    print(0)
else:
    last = a[-1]
    for i in range(1,last+1):
        cnt = c[i]
        if cnt==0:
            ans = 0
            break
        else:
            ans *= ((now**cnt)%998244353)
            ans %= 998244353
            now = cnt
    print(ans)
    
    


Measured memory_bytes: 19936
fun main(args: Array<String>) = abc156d()

fun abc156d() {
    val (n, a, b) = readLine()!!.split(' ').map { it.toInt() }

    var answer = Mint(2).modPow(n.toLong())
    answer -= 1
    answer -= comb(n, a)
    answer -= comb(n, b)

    println(answer)
}

private const val MOD = (1e9 + 7).toLong()

private fun modPow(n: Long, p: Long): Long {
    var x = n
    var y = p
    var result = 1L
    x %= MOD
    while (y > 0) {
        if (y % 2 == 1L)
            result = (result * x) % MOD
        y = y shr 1
        x = (x * x) % MOD
    }
    return result
}

// useful for big N, and small K
private fun comb(n: Int, k: Int): Long {
    if (n < k) return 0
    val min = Math.min(k, n - k)
    var value = 1L
    for (i in 1L..min) {
        value *= n - i + 1
        value %= MOD
        value *= modPow(i, MOD - 2)
        value %= MOD
    }
    return value
}

private class Mint(value: Long = 0L) {
    constructor(other: Mint) : this(other.value)

    private val value = if (value < 0) (value % MOD) + MOD else value % MOD
    operator fun unaryPlus() = this
    operator fun unaryMinus() = Mint(MOD - this.value)
    operator fun inc() = this.plus(1)
    operator fun dec() = this.minus(1)
    operator fun plus(other: Long) = Mint(this.value + other)
    operator fun plus(other: Mint) = this.plus(other.value)
    operator fun minus(other: Long) = Mint(this.value - other)
    operator fun minus(other: Mint) = this.plus(-other)
    operator fun times(other: Long) = Mint(this.value * other)
    operator fun times(other: Mint) = this.times(other.value)
    operator fun div(other: Long) = this.times(modPow(other, MOD - 2))
    operator fun div(other: Mint) = this.div(other.value)
    fun modPow(other: Long) = Mint(modPow(this.value, other))
    override fun toString() = this.value.toString()
    override fun hashCode() = value.hashCode()
    override fun equals(other: Any?): Boolean {
        if (this === other) return true
        if (javaClass != other?.javaClass) return false
        other as Mint
        return value == other.value
    }
}


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

#define rep(i,n) for (int i = 1; i <= n; i++)
#define ll long long

using namespace std;

int a[10001];

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

    rep(x,99) rep(y,99) rep(z,99) {
        int xx = pow(x, 2) + pow(y, 2) + pow(z, 2) + x * y + y * z + z * x;
        if (xx > 10000) continue;
        a[xx]++;
    }

    rep(i,n) cout << a[i] << endl;
}


Measured memory_bytes: 3552
from collections import deque
from copy import copy as dc
import sys

def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(m)]
    g = [[] for i in range(n+1)]
    for i in ab:
        g[i[0]].append(i[1])
        g[i[1]].append(i[0])
    que = deque()
    que.append([1,-1,0,set([1])])
    ans = 0
    while que:
        v, p, cnt, check = que.popleft()
        if cnt >= n - 1:
            if len(check) == n:
                ans += 1
            continue
        for nv in g[v]:
            if nv == p:
                continue
            a = dc(check)
            a.add(nv)
            que.append([nv, v, cnt+1, a])
    print(ans)

if __name__ == "__main__":
    main()


Measured memory_bytes: 195692
#include <bits/stdc++.h>
    using namespace std;
    long long  N,A,B;
    long long value[51];
    bool comp(long long a,long long b)
    {
        return a>b?true:false;
    }

    long long dp[51][51];

    void init()
    {
    	memset(dp,0,sizeof(dp));
    	dp[0][0]=1;
    	for(int i=1;i<=50;i++)
    	{
    		dp[i][0]=1;
    		for(int j=1;j<=i;j++)
    			dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
    	}
    }
    int main(void)
    {

        cin>>N>>A>>B;
        init();
        for(int i=0;i<N;i++)
        {
            cin>>value[i];
        }
        sort(value,value+N,comp);
        double sum=0.0;
        for(int i=0;i<=A-1;i++)
        {
            sum+=value[i];
        }
        long long  num=0,k=0;
    		for(int i=0;i<N;i++)
    		{
    			if(value[i]==value[A-1])
    			{
    				num++;
    				if(i<A)
    					k++;
    			}
    		}
    		long long ans=0;
    		if(k==A)//前A个相同,可以增加个数
    		{
    			for(int i=A;i<=B;i++)
    				ans+=dp[num][i];
    		}
    		else
    			ans+=dp[num][k];


        printf("%.15f\n",sum/A);
        cout <<ans <<endl;
        return 0;
    }


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

using namespace std;
#define ll long long
const int mxN=1e5;

int main(){
//#ifndef ONLINE_JUGDE
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//#endif
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int t;
	cin>>t;
	cout<<!t;
	return 0;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;

const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll INF = 1e16;
const ld EPS = 1e-11;
const ld PI = acos(-1.0L);
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define repr(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repe(i, l, r) for (ll i = (l); i < (r); i++)
#define reper(i, l, r) for (ll i = (r)-1; i >= (l); i--)

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

void init() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}
//--------------------------------------------------------------------------------//

int main() {
    init();
    ll d, r;
    ld f;
    ll a, b;
    cin >> a >> b;
    d = a / b;
    r = a % b;
    f = a / (ld)b;
    cout << d << " " << r << " " << f << endl;
}


Measured memory_bytes: 3256
#include<iostream>

using namespace std;

int cell[16][16];
int n;

void init()
{
	for(int x=0;x<n;x++){
		for(int y=0;y<n;y++){
			cell[x][y]=-1;
		}
	}
}

void solve()
{
	init();
	int x,y;
	x=(n-1)/2;
	y=x+1;
	cell[x][y]=1;
	for(int i=2;i<=n*n;i++){
		x++;
		y++;
		if(x>=n){
			x=0;
		}
		if(y>=n){
			y=0;
		}
		if(cell[x][y]!=-1){
			x--;
			y++;
			if(y>=n){
				y=0;
			}
			if(x<0){
				x=n-1;
			}
		}
		cell[x][y]=i;
	}
}

void draw()
{
	for(int y=0;y<n;y++){
		for(int x=0;x<n;x++){
			cout.width(4);
			cout<<cell[x][y];
		}
		cout<<endl;
	}
}

int main(void)
{
	while(1){
		cin>>n;
		if(n==0){
			break;
		}
		solve();
		draw();
	}
	return 0;
}

Measured memory_bytes: 1172
#include <iostream>
using namespace std;
int main(){
	char ball[10][8] = {{'*',' ','=',' ','*','*','*','*'},
											{'*',' ','=','*',' ','*','*','*'},
											{'*',' ','=','*','*',' ','*','*'},
											{'*',' ','=','*','*','*',' ','*'},
											{'*',' ','=','*','*','*','*',' '},
											{' ','*','=',' ','*','*','*','*'},
											{' ','*','=','*',' ','*','*','*'},
											{' ','*','=','*','*',' ','*','*'},
											{' ','*','=','*','*','*',' ','*'},
											{' ','*','=','*','*','*','*',' '}};
	string i;
	int b = 0;
	while(cin >> i,!cin.eof()){
		if(b)cout<<endl;
		else{b=1;}
		while(i.size() < 5)i = '0' + i;
		for(int k=0;k<8;k++){
			for(int l=0;l<5;l++){
				cout << ball[i[l]-'0'][k];
			}
			cout << endl;
		}
	}
}

Measured memory_bytes: 896
#include <stdio.h>
#include <string.h>

int main(void)
{
    int n = 0;
    char S[10];
    scanf("%s", S);

    for (int i = 0; i < 4; i++)
    {
        if ('+' == S[i])
        {
            n++;
        }
        else
        {
            n--;
        }
    }
    printf("%d\n", n);
}

Measured memory_bytes: 128
import java.util.Scanner;

class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int l = sc.nextInt();
		int r = sc.nextInt();
		long min = 2019;

		for(int i=0; i<2019; i++){
			long x = l+i;
			for(int j=i+1; j<2019; j++){
				long y = l+j;
				if(x>r || y>r) break;
				min = Math.min(min, (x*y)%2019);
			}
		}
		System.out.println(min);

	}
}


Measured memory_bytes: 21712
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define INF (1LL<<50)
#define MOD 1000000007

int main(){
    int N;
    cin >> N;
    int a;
    vector<int> A(N+1);
    rep(i,N){
        cin >> a;
        A[a]=i;
    }
    rep(i,N-1){
        cout << A[i+1]+1 << " ";
    }
    cout << A[N]+1 << endl;
    return 0;
}

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

#define for0(i, n) for (ll i = 0; i < (ll)(n); ++i) // 0 based indexing
#define for1(i, n) for (ll i = 1; i <= (ll)(n); ++i) // 1 based indexing
#define forc(i, l, r) for (ll i = (ll)(l); i <= (ll)(r); ++i) // closed interver from l to r r inclusive
#define forr0(i, n) for (ll i = (ll)(n) - 1; i >= 0; --i) // reverse 0 based.
#define forr1(i, n) for (ll i = (ll)(n); i >= 1; --i) // reverse 1 based

#define ff first
#define ss second
#define pb push_back

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n;
	cin >> n;
	if(n%2 == 0)cout << n/2;
	else cout << n/2+1;

	return 0;
}


Measured memory_bytes: 256
import java.util.*;
import static java.lang.Integer.*;
//import static java.lang.Long.*;
//import static java.lang.Math.*;
import static java.lang.System.*;

public class Main {
	static int[] ans;
	static ArrayList<ArrayList<Integer>> ab;
	static HashMap<Integer, Integer> px = new HashMap<>(); 

	public static void main(String[] args) {
		int i,j;
		Scanner sc = new Scanner(in);
		int n = parseInt(sc.next());
		int m = parseInt(sc.next());
		sc.close();
		int a = m / n;
		for (i = a; i >= 1; i--) {
			if(m % i == 0) break;
		}
		out.println(i);
	}
}


Measured memory_bytes: 21844
while True:
    n, x = map(int,input().split())
    if n + x == 0:
        exit()
    r = 0
    for i in range(n):
        for j in range(i+1,n):
            for k in range(j+1,n):
                if i + j + k + 3 == x:
                    r += 1
    print(r)


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

int main()
{
  string S[3];
  for (auto & s : S)
    cin >> s;
  int cnt[3] = {};
  int i = 0;
  for (; ; )
  {
    if (S[i].size() <= cnt[i])
      break;
    ++cnt[i];
    i = S[i][cnt[i] - 1] - 'a';
  }
  cout << static_cast<char>('A' + i);
  return 0;
}


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

using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef long double ld;
const ll mod = 1e9 + 7;

ll solve(void)
{
	ll k;
	cin >> k;

	queue<ll> q;
	for (ll i = 1; i <= 9; i++)
		q.push(i);

	ll cnt = 0;
	while (++cnt < k)
	{
		auto f = q.front();
		auto g = f % 10;
		auto h = f * 10;

		if (g > 0) { q.push(h + g - 1); }
		q.push(h + g);
		if (g < 9) { q.push(h + g + 1); }

		q.pop();
	}

	cout << q.front() << endl;

	return 0;
}

int main(void)
{
	while(solve()){}

	return 0;
}

Measured memory_bytes: 5156
#include <bits/stdc++.h>
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/algorithm/string/classification.hpp> // is_any_of
#include <boost/algorithm/string/split.hpp>
#include <boost/algorithm/string/join.hpp>
#include <boost/algorithm/string/replace.hpp>
#include <boost/math/tools/minima.hpp>

#define rep(i, n) for (int i = 0; i < (n); ++i)

namespace adaptor = boost::adaptors;
using namespace std;
using boost::math::tools::brent_find_minima;
using boost::irange;
using boost::algorithm::split;
using boost::algorithm::replace_all;
using boost::multiprecision::cpp_int;
using ll = long long;
using P = pair<int, int>;
using boost::algorithm::join;
// TOP


void	Main()
{
	int	n;
	cin >> n;
	vector<vector<int>>	V(2);
	int temp;
	cin >> temp;
	V.at(0).push_back(temp);
	for (int i = 1; i < n; i++)
	{
		int temp;
		cin >> temp;
		V.at(0).push_back(temp + V.at(0).at(i - 1));
	}
	cin >> temp;
	V.at(1).push_back(temp + V.at(0).at(0));
	for (int i = 1; i < n; i++)
	{
		int temp;
		cin >> temp;
		V.at(1).push_back(temp + max(V.at(0).at(i), V.at(1).at(i - 1)));
	}
	cout << V.at(1).at(n - 1) << endl;
}
// END
















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



Measured memory_bytes: 256
/**
*    author:  yuya1234
*    created: 13.07.2020 14:46:51
**/

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define FORV(i,v) for(auto i=v.begin(); i!=v.end();i++)

#define SORT(s) sort((s).begin(),(s).end())
#define SORTD(s) sort((s).rbegin(),(s).rend())
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define SZ(x) ((int)(x).size())
#define MEMSET(v, h) memset((v), h, sizeof(v))

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; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  //std::cout << std::fixed << std::setprecision(15);

  int n,k,s;
  cin>>n>>k>>s;

  int kari=100000;
  while(s%kari==0){
    kari--;
  }

  REP(i,n-1){
    if(k>0)cout<<s<<" ";
    else cout<<kari<<" ";
    k--;
  }

  if(k>0)cout<<s<<endl;
  else cout<<kari<<endl;

  return 0;
}


Measured memory_bytes: 3604
n,x=gets.chomp.split(' ').map(&:to_i)
array=gets.chomp.split(' ').map{|i| (x - (i.to_i)).abs }
def gcd(a,b)
if a<b
gcd(b,a) 
else
a,b=b,a%b while b>0
a
end
end
c=array.length
if c==1 
puts array
elsif c==2
p gcd(array[0],array[1])
else
k=array[0]
(c-2).times{|i| k=gcd(k,array[i+1])}
p k
end


Measured memory_bytes: 9484
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPS(i, r, n) for (int i = (r); i < (n); ++i)

int in() {int x; cin>>x; return x;}
string stin() {string s; cin>>s; return s;}
int n, m, q;
int a[55], b[55], c[55], d[55];
int dfs(int rest, vector<int> v, int last_element = 0) {
  if(last_element) {
    v.push_back(last_element);
  } else {
    last_element = 1;
  }
  if(rest == 0) {
    int ret = 0;
    REP(i, q) {
      if(v[b[i]] - v[a[i]] == c[i]) {
        ret += d[i];
      }
    }
    return ret;
  }

  int ans = 0;
  REPS(i, last_element, m+1) ans = max(ans, dfs(rest-1, v, i));
  return ans;
}
/***** MAIN *****/
signed main() {
  cin >> n >> m >> q;
  REP(i,q) {
    cin >> a[i] >> b[i] >> c[i] >> d[i];
    --a[i]; --b[i];
  }
  cout << dfs(n, vector<int>());
  cout << "\n";
  return 0;
}
/***** MAIN *****/


Measured memory_bytes: 3628
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <string>
#include <vector>

using namespace std;

int check(int x, int y, const vector< vector<int> > &v)
{
    if (x < 0 || y < 0) return 0;
    else return v[x][y];
}

int main()
{
    int N, M, Q;
    if (scanf("%d%d%d", &N, &M, &Q) < 3) return 0;

    vector<string> S(2000);

    for (int i = 0; i < N; i++)
    {
        char tmp[2001];
        if (scanf("%s", tmp) < 1) return 0;
        S[i] = tmp;
    }

    vector< vector<int> > BH(N, vector<int>(M));

    for (int i = 0; i < N; i++)
    {
        int bk = 0;
        for (int j = 0; j < M; j++)
        {
            int s = S[i][j] - '0';
            BH[i][j] += bk + s;
            bk = BH[i][j];

            if (0 <= i - 1) BH[i][j] += BH[i - 1][j];
        }
    }

    vector< vector<int> > H(N, vector<int>(M - 1));

    for (int i = 0; i < N; i++)
    {
        int bk = 0;
        for (int j = 1; j < M; j++)
        {
            int sl = S[i][j - 1] - '0';
            int sr = S[i][j] - '0';
            H[i][j - 1] += sl & sr ? bk + 1 : bk;
            bk = H[i][j - 1];

            if (0 <= i - 1) H[i][j - 1] += H[i - 1][j - 1];
        }
    }

    vector< vector<int> > V(N - 1, vector<int>(M));

    for (int i = 0; i < M; i++)
    {
        int bk = 0;
        for (int j = 1; j < N; j++)
        {
            int su = S[j - 1][i] - '0';
            int sd = S[j][i] - '0';
            V[j - 1][i] += su & sd ? bk + 1 : bk;
            bk = V[j - 1][i];

            if (0 <= i - 1) V[j - 1][i] += V[j - 1][i - 1];
        }
    }

    for (int i = 0; i < Q; i++)
    {
        int x1, y1, x2, y2;
        if (scanf("%d%d%d%d", &x1, &y1, &x2, &y2) < 4) return 0;

        int b =
            BH[x2 - 1][y2 - 1] - check(x2 - 1, y1 - 2, BH)
                - check(x1 - 2, y2 - 1, BH) + check(x1 - 2, y1 - 2, BH);

        int h =
            check(x2 - 1, y2 - 2, H) - check(x2 - 1, y1 - 2, H)
                - check(x1 - 2, y2 - 2, H) + check(x1 - 2, y1 - 2, H);

        int v =
            check(x2 - 2, y2 - 1, V) - check(x2 - 2, y1 - 2, V)
                - check(x1 - 2, y2 - 1, V) + check(x1 - 2, y1 - 2, V);

        printf("%d\n", b - h - v);
    }

    return 0;
}


Measured memory_bytes: 52864
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define mod 1000000007
#define int long long int
#define N 200005
void fast(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int n,t;
int dp[3003][3003];
vector<pair<int,int> > a;
int fun(int pos,int rem){
  // cout<<pos<<" "<<rem<<endl;
  if(rem<=0)return 0;
  if(pos==n)return 0;
  int res=dp[pos][rem];
  if(res!=-1)return res;
  res=0;
  res=max(res,a[pos].second+fun(pos+1,rem-a[pos].first));
  res=max(res,fun(pos+1,rem));
  dp[pos][rem]=res;
  return res;
}
main()
{
  cin>>n>>t;
  for(int i=0;i<n;i++){
    int x,y;
    cin>>x>>y;
    a.pb(mp(x,y));
  }
  sort(a.begin(),a.end());
  memset(dp,-1,sizeof(dp));
  cout<<fun(0,t)<<endl;
}

Measured memory_bytes: 70912
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
#include<map>
#include<cstring>
#include<unordered_map>
#include<set>
#define int long long
using namespace std;

set<int>S;
int x[200000];
signed main() {
	int sum = 0;
	int a; cin >> a;
	S.insert(-1); S.insert(a);
	for (int i = 0; i < a; i++) {
		int j; scanf("%lld", &j);
		x[j - 1] = i;
	}
	for (int i = 0; i < a; i++) {
		S.insert(x[i]);
		auto n = S.find(x[i]), m = n;
		n--; m++;
		sum += (i + 1)*(*m - x[i])*(x[i] - *n);
	}
	cout << sum << endl;
}

Measured memory_bytes: 11388
let rec digits_sum = function
  | 0 -> 0
  | n -> n mod 10 + digits_sum (n / 10)

let () = Scanf.scanf "%d" @@ fun n ->
  Array.init (n - 1) (fun a -> a + 1, n - a - 1)
  |> Array.map (fun (a, b) -> digits_sum a + digits_sum b)
  |> Array.fold_left min max_int
  |> Printf.printf "%d\n"

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

using namespace std;

using int64 = long long;

bool check(string s) {
  while(s.size() > 3) {
    char c = 'B';
    if(s.substr(0, 3) == "ABC") c = 'A';
    else if(s.substr(s.size() - 3) == "ABC") c = 'C';
    string nxt;
    for(int i = 0; i < s.size(); i++) {
      if(s.substr(i, 3) == "ABC") nxt += c, i += 2;
      else if(s[i] == c) return false;
      else nxt += s[i];
    }
    if(nxt == s) return false;
    s = nxt;
  }
  return s == "ABC";
}

int main() {
  string S;
  cin >> S;
  puts(check(S) ? "Yes" : "No");
}



Measured memory_bytes: 3248
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;

const int MOD = 1000000007;
const int INF = 1001001001;

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

int N, Q;
vector<vector<int>> graph(200020);
vector<int> ans(200020, 0);
vector<int> tree(200200, 0);

void dfs(int n, int prev=-1) {
    for(auto p: graph[n]) {
        if(p != prev) {
            ans[p] += ans[n];
            dfs(p, n);
        }
    }
}

int main() {
    cin >> N >> Q;

    for(int i = 0; i < N - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--;b--;
        graph[b].emplace_back(a);
        graph[a].emplace_back(b);
    }

    for(int i = 0; i < Q; i++) {
        int p, x;
        cin >> p >> x;
        p--;
        ans[p] += x;
        tree[p] += x;
    }

    dfs(0);

    for(int i = 0; i < N; i++) {
        cout << ans[i] << " ";
    }

    cout << endl;
}


Measured memory_bytes: 24320
#include <bits/stdc++.h>
#define REP(i,n) for (int i=0; i<(n); ++i)
#define REPR(i,n,m) for (int i=(n); i>=(m); --i)
using namespace std;
using LL = long long;
using LD = long double;
using PLL = pair<long long, long long>;
using PLD = pair<long double, long double>;
using VLL = vector<long long>;
using VLD = vector<long double>;
using VPLD = vector<PLD>;

const int INF = numeric_limits<int>::max();

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

    LL n; cin >> n;
    VLL ans(n,0);

    for(LL i=1;i<=100;i++) {
        for(LL j=1;j<=100;j++) {
            for(LL k=1;k<=100;k++) {
                LL tmp = 0;
                tmp = i*i+j*j+k*k+i*j+j*k+k*i;
                if ((0<=tmp)&&(tmp<=n)) {
                    ans[tmp]++;
                }
            }
        }
    }

    for(int i=1;i<=n;i++) cout << ans[i] << endl;

    return 0;
}

Measured memory_bytes: 3616
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t) for(ll i = (ll)(s); i < (ll)(t); i++)
#define rrep(i,s,t) for(ll i = (ll)(s-1);(ll)(t) <= i; i--)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
constexpr ll INF = numeric_limits<ll>::max()/4;
constexpr ll n_max = 4e6+10;
#define int ll

template <typename A, typename B>
string to_string(pair<A, B> p);
string to_string(const string &s) {return '"' + s + '"';}
string to_string(const char *c) {return to_string((string) c);}
string to_string(bool b) {return (b ? "true" : "false");}
template <size_t N>
string to_string(bitset<N> v){
    string res = "";
    for(size_t i = 0; i < N; i++) res += static_cast<char>('0' + v[i]);
    return res;
}
template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for(const auto &x : v) {
        if(!first) res += ", ";
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p){return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}

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

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

void print(vector<T> &vec, ll k){
    ll n = vec.size();
    k = min(k, n);
    for(int i = 0; i < k-1; i++) cout << vec[i] << " ";
    cout << vec[k-1] << endl;
}
template <class T>
void print(vector<vector<T>> &vec, ll k){
    ll n = vec[0].size();
    k = min(k, n);
    for(auto &i : vec)print(i, k);
}
template<size_t N>
void print(bitset<N> &bs, ll k){
    ll n = min(ll(N), k);
    for(int i = 0; i < k-1; i++){
        cout << bs[i];
    }
    cout << endl;
}
signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

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

    bitset<n_max> dp;
    dp[0] = 1;
    rep(i,0,n){
        dp |= dp << a[i];
    }

    // print(dp, 10);
    rep(i, (sum + 1) / 2, n_max) {
        if(dp[i]){
            cout << i << "\n";
            return 0;
        }
    }
}

Measured memory_bytes: 5136
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
#define endl "\n"
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();
// freopen("input.txt", "r", stdin);

int main() {
    int t;
    cin >> t;
    while(t--) {
        ll n, a, b, c, d;
        cin >> n >> a >> b >> c >> d;
        unordered_map<ll, ll> dp;
        vector<ll> cost = {a, b, c};
        ll thres = LONG_LONG_MAX / d;
        auto dfs = [&](auto& self, ll x) -> ll {
            if (x == 0) return 0;
            if (x == 1) return d;
            // cout << "compute " << x << endl;
            if (dp.count(x) > 0) return dp[x];
            ll cur = (x <= thres) ? x*d : 1e18;
            int i = 0;
            for(ll cand: {2, 3, 5}) {
                if (x % cand == 0) {
                    cur = min(cur, self(self, x/cand)+cost[i]);
                } else {
                    ll rem = x % cand;
                    ll rem2 = cand - rem;
                    cur = min(cur, self(self, (x+rem2)/cand) + cost[i] + rem2*d);
                    if (x - cand > 0) {
                        cur = min(cur, self(self, x/cand) + cost[i] + rem*d);
                    } else {
                        cur = min(cur, rem*d);
                    }
                }
                i++;
            }
            dp[x] = cur;
            return dp[x];
        };
        cout << dfs(dfs, n) << endl;
    }    
    return 0;
}


Measured memory_bytes: 4100
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <set>
#include <queue>
#include <map>
#include <numeric>
#include <functional>
#include <math.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

#define INF ((int)1e9)
#define INFLL ((ll)1e18)
#define MOD (1000000007LL)


int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    int N, K;
    cin >> N >> K;
    vector<int> P(N);
    for (int n = 0; n < N; ++n) cin >> P[n];
    
    if (N == K) {
        cout << 1 << endl;
        return 0;
    }
    
    vector<int> vnMin(N-K), vnMax(N-K);
    deque<int> deqMin, deqMax;
    for (int n = 0; n < N; ++n) {
        while (!deqMin.empty()) {
            if (P[deqMin.back()] > P[n]) {
                deqMin.pop_back();
            } else {
                break;
            }
        }
        deqMin.push_back(n);
        if (n >= K) {
            vnMin[n-K] = P[deqMin[0]];
            if (deqMin.front() == n-K) {
                deqMin.pop_front();
            }
        }
        
        while (!deqMax.empty()) {
            if (P[deqMax.back()] < P[n]) {
                deqMax.pop_back();
            } else {
                break;
            }
        }
        deqMax.push_back(n);
        if (n >= K) {
            vnMax[n-K] = P[deqMax[0]];
            if (deqMax.front() == n-K) {
                deqMax.pop_front();
            }
        }
    }
    
    int nCount = 0;
    int nOrigInc = 0;
    vector<int> vnOrigInc(N-K+1, 0);
    for (int n = 0; n < N-1; ++n) {
        if (P[n] < P[n+1]) {
            ++nCount;
        }
        if (n >= K-1 && P[n-K+1] < P[n-K+2]) {
            --nCount;
        }
        if (nCount == K-1) {
            ++nOrigInc;
            vnOrigInc[n-K+2] = 1;
        }
    }
    
    int nRes = N-K+1;
    for (int n = 0; n+K < N; ++n) {
        if (!vnOrigInc[n] && P[n] == vnMin[n] && P[n+K] == vnMax[n]) {
            --nRes;
        }
    }
    
    if (nOrigInc > 1) {
        nRes -= (nOrigInc - 1);
    }
    cout << nRes << endl;

    return 0;
}


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

/* 大文字を小文字に変換 */
char tolower(char c) {return (c + 0x20);}
/* 小文字を大文字に変換 */
char toupr(char c) {return (c - 0x20);}

// if('A'<=s[i] && s[i]<='Z') s[i] += 'a'-'A';

/*
string s = "abcdefg"
s.substr(4) "efg"
s.substr(0,3) "abc"
s.substr(2,4) "cdef"

// イテレータ要素のインデックス
distance(A.begin(), itr);
*/

const int INF = 1000100100;

int main()
{
    int N; cin >> N;
    if(N % 1000 == 0) cout << 0 << endl;
    else cout << (1000*(N/1000+1) - N) << endl;
}

Measured memory_bytes: 3608
import sys
input = sys.stdin.readline

import math

def main():
    a,b,n = map(int, input().split())

    if b > n:
        print(math.floor(a*n/b))

    else:
        print(math.floor(a*(b-1)/b) - a*math.floor((b-1)/b))

if __name__ == '__main__':
    main()


Measured memory_bytes: 62220
n, k = map(int, input().split())
lst_h = list(map(int, input().split()))


dp = [float("INF")] * n
dp[0] = 0
for i in range(n):
    for j in range(1, k + 1):
        if i + j > n - 1:
            break
        dp[i + j] = min(dp[i + j], dp[i] + abs(lst_h[i] - lst_h[i + j]))


ans = dp[n - 1]
print(ans)

Measured memory_bytes: 55136
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long N,A,B;cin>>N>>A>>B;
  long set=A+B;
  long X=N/set;
  long Y=N-X*set;
  long Z=min(Y,A);
  cout<<X*A+Z<<endl;
}

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;

//テストケースはあんまり見ないほうが良い。デバッグする能力が必要.
int main(){
    int n;
    cin >> n;
    vector<int> d(n);
    rep(i,n)cin >> d[i];
    int ans=0;
    rep(i,n-1){
        for(int j=i+1;j<n;++j){
            ans += d[i]*d[j];
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
a = [0]*(n+1)
for i in range(1, n+1):
    a[i] = int(input())

index = 1
ret = 1
for i in range(n):
    next = a[index]
    if next == 2:
        print(ret)
        break
    if next == -1:
        print(-1)
        break
    ret += 1
    a[index] = -1
    index = next



Measured memory_bytes: 6900
import sys
sys.setrecursionlimit(1000000)

MOD = 10**9 + 7

def ex_euclid(a,b,c,d):
    if (b == 1) : return d
    x = a // b
    y = a % b
    return ex_euclid(b,y,d,(c[0]-x*d[0],c[1]-x*d[1]))
    
 
def mod_inv(a,p):
    x = ex_euclid(p,a,(1,0),(0,1))
    return x[1] % p

n,a,b,c,d = map(int,input().split())

gp = b-a+1

dp = [[-1 for j in range(n+1)] for i in range(gp)]

tb1=[0,1]
tb2=[1] #便宜上0の逆元は0にする
for i in range(2,n+1):
    tb1.append((tb1[i-1]*i) % MOD)
for i in range(1,n+1):
    tb2.append(mod_inv(tb1[i],MOD))
    

for i in range(gp):dp[i][0] = 1


def dfs(sum,k):
    summ = sum
    if(k < 0):
        if (sum != 0):return 0
        else : return 1
    if dp[k][sum] != -1: return dp[k][sum]
    kk = k+a
    temp = dfs(sum,k-1)
    temp1 = 1
    for i in range(c-1):
        if (sum < 0):break
        temp1 = (temp1 * tb1[sum] * tb2[sum-kk]*tb2[kk]) % MOD 
        sum -= kk
    for i in range(c,d+1):
        if(sum-kk < 0) : break
        temp1 = (temp1 * tb1[sum] * tb2[sum-kk]*tb2[kk]) % MOD
        sum -= kk
        temp = (temp + temp1*dfs(sum,k-1)*tb2[i]) % MOD

    dp[k][summ] = temp
    return temp
    

        
ans = dfs(n,gp-1)



print(ans)

Measured memory_bytes: 127964
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define zero_pad(num) setfill('0') << std::right << setw(num)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;

int main() {
    int n;
    cin >> n;
    if(n >= 64) cout << 64 << endl;
    else if(n >= 32) cout << 32 << endl;
    else if(n >= 16) cout << 16 << endl;
    else if(n >= 8) cout << 8 << endl;
    else if(n >= 4) cout << 4 << endl;
    else if(n >= 2) cout << 2 << endl;
    else cout << 1 << endl;
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> V;
const long long MOD=1000000007LL;
const long long INFL=1LL << 60;
const int INF=1<<29;


int main() {
    while(1){
        int N; cin >>N;
        if(!N)
            break;
        int T=24*60*60;
        V time(T,0);
        for(int i=0;i<N;i++){
            string S,G;
            cin >>S>>G;
            int S_time,G_time;
            S_time=(S[0]-'0')*36000+(S[1]-'0')*3600
            +(S[3]-'0')*600+(S[4]-'0')*60+(S[6]-'0')*10
            +S[7]-'0';
            G_time=(G[0]-'0')*36000+(G[1]-'0')*3600
            +(G[3]-'0')*600+(G[4]-'0')*60+(G[6]-'0')*10
            +G[7]-'0';
            time.at(S_time)++;
            time.at(G_time)--;
        }
        for(int i=0;i<T;i++){
            if(0<i)time.at(i)+=time.at(i-1);
        }
        int M=0;
        for(int i=0;i<T;i++){
            if(M<time.at(i))M=time.at(i);
        }
        cout <<M<<endl;
    }
    return 0;
}


Measured memory_bytes: 3556
#include <iostream>
#include <cctype>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <string>
#include <functional>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <bitset>
#define pb push_back
#define YES cout<<"YES"<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define No cout<<"No"<<endl
#define INF (1<<10)
#define MOD 1000000007
typedef long long ll;
using namespace std;

int main() {
    string a,b;
    cin>>a>>b;
    if(a.length()>b.length())cout<<"GREATER"<<endl;
    else if(a.length()<b.length())cout<<"LESS"<<endl;
    else{
      for(int i=0;i<a.length();i++){
        if(a[i]>b[i]){
          cout<<"GREATER"<<endl;
          return 0;
        }
        else if(a[i]<b[i]){
          cout<<"LESS"<<endl;
          return 0;
        }
      }
      cout<<"EQUAL"<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
import sys
input=sys.stdin.readline

def main():
    N, W = map(int,input().split())
    WG = [0]
    V = [0]
    for i in range(N):
        w, v = map(int,input().split())
        WG.append(w)
        V.append(v)
    
    dp = [[float('inf')]*(max(V)*N+1) for _ in range(N+1)]
    dp[0][0] = 0
    
    for i in range(1,N+1):
        for v in range(0,max(V)*N+1):
            if v-V[i] < 0:
                dp[i][v] = dp[i-1][v]
                continue
            dp[i][v] = min(dp[i-1][v], dp[i-1][v-V[i]]+WG[i])
    
    ans = 0
    for i in range(max(V)*N+1):
        if dp[N][i] <= W:
            ans = i
            
    print(ans)
    
if __name__ == '__main__':
    main()

Measured memory_bytes: 249592
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

#define MIN_INT -2147483648
#define MAX_INT 2147483647
#define MIN_LONG -9223372036854775808L
#define MAX_LONG 9223372036854775807L
#define PI 3.141592653589793238462643383279502884L

#define long long long int

using std::vector;
using std::map;
using std::set;
using std::string;
using std::pair;
using std::cin;
using std::cout;
using std::cerr;

// @author: pashka

vector<vector<bool>> go(int n, int d) {
    vector<vector<bool>> a(2 * n, vector<bool>(2 * n));
    if (d % 2 == 1) {
        for (int i = 0; i < 2 * n; i++) {
            for (int j = 0; j < 2 * n; j++) {
                if ((i + j) % 2) {
                    a[i][j] = true;
                }
            }
        }
    } else {
        if (d % 4 != 0) {
            for (int i = 0; i < 2 * n; i++) {
                for (int j = 0; j < 2 * n; j++) {
                    if (i % 2) {
                        a[i][j] = true;
                    }
                }
            }
        } else {
            auto aa = go((n + 1) / 2, d / 4);
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (aa[i][j]) {
                        for (int ii = 0; ii < 2; ii++) {
                            for (int jj = 0; jj < 2; jj++) {
                                a[2 * i + ii][2 * j + jj] = true;
                            }
                        }
                    }
                }
            }

        }
    }
    return a;
}

int main() {
    std::ios::sync_with_stdio(false);

    int n, d1, d2;
    cin >> n >> d1 >> d2;
    auto a1 = go(n, d1);
    auto a2 = go(n, d2);

    int s = n * n;
    for (int i = 0; i < 2 * n; i++) {
        for (int j = 0; j < 2 * n; j++) {
            if (!a1[i][j] && !a2[i][j] && s > 0) {
                s--;
                cout << i << " " << j << "\n";
            }
        }
    }

    return 0;
}

Measured memory_bytes: 1152