akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n) ;i++)
using namespace std;
using p=pair<int,int>;

int main() {
  vector<int>a(3);
  rep(i,3){
    cin >> a.at(i);
  }
  int l,m,n ;
  l=a.at(0);
  m=a.at(1);
  n=a.at(2);
  a.at(0)=n;
  a.at(1)=l;
  a.at(2)=m;
  
  rep(j,3){ 
   cout << a.at(j) << endl;
  }
  
  

}
 

Measured memory_bytes: 3600
#define _USE_MATH_DEFINES

#include <iostream>
#include <algorithm> // min()
#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <stack>
#include <tuple>
#include <climits> // INT_MAX
#include <cmath> // ceil()
#define rep(i, n) for (int i = 0; i < n; ++i)

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;
using Graph = vector<vector<int>>;


int main() {
	int h1, h2, m1, m2, k;
	cin >> h1 >> m1 >> h2 >> m2 >> k;

	auto time = h2 * 60 + m2 - (h1 * 60 + m1);

	cout << time - k << endl;
}

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

typedef pair<int,int> P;

signed main(){
  int N,K,a,b;cin>>N>>K;
  std::vector<P> v(N);
  for(int i;i<N;i++){
    cin>>a>>b;
    v[i]=P(a,b);
  }
  sort(v.begin(),v.end());
  int cnt=0;
  for(int i=0;i<N;i++){
    cnt+=v[i].second;
    if(cnt>=K){
      cout<<v[i].first<<endl;
      return 0;
    }
  }
}


Measured memory_bytes: 1792
from collections import deque
from heapq import heappop, heappush, heapify
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7


def main():
  N, M = map(int, readline().split())
  AB = [[int(x) for x in readline().split()] for _ in range(N)]
  #i日で報酬が得られるもののリスト
  days = [[0] for _ in range(M)]
  for ab in AB:
    if ab[0]-1>=M:
      continue
    else:
      days[ab[0]-1].append(ab[1])
  stack = deque(days)
  q = []
  ans = 0
  while stack:
    x = stack.popleft()
    for y in x:
      heappush(q,-y)
    z = heappop(q)
    ans += z
  print(-ans)
  
  
      
if __name__ == '__main__':
  main()

Measured memory_bytes: 37220
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;

/*
<url:https://cf16-exhibition-final-open.contest.atcoder.jp/tasks/cf16_exhibition_final_b>
問題文============================================================
 すぬけ君は、誕生日プレゼントに三角形をもらいました。
 三頂点の座標は (x1,y1), (x2,y2), (x3,y3) でした。
 
 すぬけ君は、三角形の内部に半径の等しい二つの円を、重ならないように描きたいです (二円が点で接していてもいいです)。
 円の半径の最大値を求めてください。

=================================================================

解説=============================================================

 色々計算すると
 三角形の各辺の長さを a,b,c
 内接円の半径を r
 M := max(a,b,c)
 とすると
 
 M(2+M/r)) が答え
 
 
 三角形の内部で辺に接するように　半径 x の円を描いた時、その円の中心の軌跡をたどると
 内部に三角形と相似になる　小さい　三角形ができる
 この時、その小さな三角形の二点を用いて 2x 以上の長さとなるようであれば 半径 x の円を二つ描くことができる
 あとは、それをギリギリまで詰めると　↑の式が出てくる
================================================================
*/

typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-9, pi = acos(-1.0);
namespace std {
    bool operator<(const Point &lhs, const Point &rhs) {
        if (lhs.real() < rhs.real() - eps) return true;
        if (lhs.real() > rhs.real() + eps) return false;
        return lhs.imag() < rhs.imag();
    }
}
Point input_point() { ld x, y; cin >> x >> y; return Point(x, y); } // 点の入力
bool eq(ld a, ld b) { return (abs(a - b) < eps); } // 誤差つき等号判定
ld dot(Point a, Point b) { return real(conj(a) * b); } // 内積
ld cross(Point a, Point b) { return imag(conj(a) * b); } // 外積

ld solve(){
    Point p1 = input_point(), p2 = input_point(), p3 = input_point();
    ld a = abs(p1-p2), b = abs(p2-p3), c = abs(p3-p1);
    ld S = abs(cross(p2-p1,p3-p1)/2);
    ld r = 2*S/(a+b+c);
    ld M = max({a,b,c});
    ld ret = M/(2+M/r);
    return ret;
}
int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
    cout << fixed << setprecision(15) << solve() << endl;
	return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<numeric>
#include<math.h>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<iomanip>
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define ll long long
#define pll pair<ll,ll>
#define rep(i,from,to) for(int i=from;i<to;i++)
#define repd(i,from,till) for(int i=from;i>=till;i--)
#define waste ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define inf 1e9+1
#define mod 1e9+7
#define inf1 1e18+1
#define pie 3.14159265358979323846
#define N 100005
using namespace std;

int solve(){
	int n;
	cin>>n;
	pair <int,int> a[n];
	rep(i,0,n){
		cin>>a[i].second>>a[i].first;
	}
	sort(a,a+n);
	int now=0;
	rep(i,0,n){
		if(now+a[i].second>a[i].first){
			cout<<"No"<<endl;
			return 0;
		}
		else now=now+a[i].second;
	}
	cout<<"Yes"<<endl;
}
int main()
{
	waste;
	int t;
	//cin>>t;
	t=1;
	while(t--){
		solve();
	}
}


Measured memory_bytes: 1792
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[] AC = new int[N];
		int[] penalty = new int[N];
		int ACCnt = 0;
		int penaltyCnt = 0;
		for(int i = 0; i < M; i++){
		    int p = sc.nextInt() - 1;
		    String s = sc.next();
		    if(AC[p] == 1) continue;
		    if(s.equals("AC")){
		        AC[p] = 1;
		        ACCnt++;
		        penaltyCnt += penalty[p];
		    }else{
		        penalty[p]++;
		    }
		}
		System.out.println(ACCnt + " " + penaltyCnt);
	}
}

Measured memory_bytes: 65084
#include<stdio.h>
#include<string.h>
#include<math.h>
#include <stdlib.h>
#include<ctype.h>


int main(){
	int N,X,Y;
	scanf("%d %d %d",&N,&X,&Y);
	
	int check[N] ;
	for(int i=0; i<N ; i++ ) {
		check[i] = 0;
	}
	for(int i=1; i<N+1; i++ ) {
		for(int j = i+1; j<N+1 ; j++ ) {
			int sakoshun = j-i;
			int sakoda = abs(j-Y) + abs(i-X) +1;
			if ( sakoda < sakoshun ) {
				check[sakoda]++;
			} else {
				check[sakoshun]++;
			}
		}
	}
	for(int i=1; i<N ; i++ ) {
		printf("%d\n",check[i]);
	}
			
	return 0;
	
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

static const int INF = 1 << 28;

#define D(x) cout << x << endl;
#define d(x) cout << x;

typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vll;

int main() {
  int n;
  cin >> n;
  int x = n * 800;
  int y = n / 15;
  y *= 200;

  D(x - y);
  
  return 0;
}


Measured memory_bytes: 764
#include<bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  int a[n];
  for(int i = 0; i < n; i++)
    cin >> a[i];
  sort(a, a + n);
  long double ans = 0;
  for(int i = 0; i < n; i++) {
    if(i == 0)
      ans = a[i];
    else ans = (ans + a[i]) / 2.0;
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>
#include <cstdio>
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stdio.h>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include <bits/stdc++.h>
#include <utility>
#include <iomanip>

#define ALL(obj) (obj).begin(), (obj).end()
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,a,b) for(int i = (a); (b) <= i; i--)
#define REP(i,n) for(int i = 0; i < (n); i++)
#define RREP(i,n) for(int i = n; n <= i; i--)
#define ABS(a) ((a < 0) ? ((-1)*(a)) : (a))
#define elif else if
#define MOD 1000000007
#define INF (1<<30)

using namespace std;

#define ld long double
#define ll long long

map <int ,int> mpa,mpb;
typedef pair<ll, ll> P;
priority_queue<P, vector<P>, greater<P>> pque;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N,M,C;
  cin >>  N >> M >> C;
  int B[M];
  for(int i=0;i<M;i++){
    cin >> B[i];
  }
  int A[N][M];
  int ans=0;
  int cnt=0;
  for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
      cin >> A[i][j];
      cnt+=A[i][j]*B[j];
    }
    if(cnt+C>0){
      ans++;
    }
    cnt=0;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
from collections import deque

def solve(k):
    v = []
    que = deque([x for x in range(1, 10)])
    while len(v) <= k:
        x = que.popleft()
        v.append(x)
        i = x % 10
        for j in range(max(0,i-1), min(10,i+2)):
            nx = 10*x + j
            que.append(nx)
    return sorted(v)[k-1]

k = int(input())
print(solve(k))


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

typedef long long ll;

#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define tt int t; cin>>t; while(t--)
#define nl cout<<"\n";
#define sp cout<<" ";
#define rep(i, a, b) for(long long i=a; i<b; i++)

const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
double PI = 4*atan(1);

int main()
{
    optimize();

    int k, a, b;

    cin>> k>> a>> b;

    cout<< ( ((b/k) *k) >= a ? "OK\n": "NG\n" );


    return 0;
}




Measured memory_bytes: 3572
#include <iostream>
#include <sstream>
#include <string>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>

using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair
#define mt make_tuple

int N, M;
int score = 1e9;

int calc_score(vector<int>& idx, vector<vector<int>>& As) {
    map<int, int> m;
    int ret = 0;
    REP(n,N) {
        ++m[As[n][idx[n]]];
        // cout << As[n][idx[n]] << ",";
        ret = max(ret, m[As[n][idx[n]]]);
    }
    // cout << endl;
    // cout << "score:" << ret << endl;
    return ret;
}

set<set<int>> taken_seen;
void dfs(vector<int>& idx, vector<vector<int>>& As, set<int>& taken) {

    auto local_score = calc_score(idx, As);
    score = min(score, local_score);

    if (SIZE(taken) == M-1) {
        return;
    }

    auto M_rem = M - SIZE(taken);
    auto best_score = (N + (M_rem - 1)) / M_rem;
    // cout << "cur_score, best_score::" << score << "," << best_score << endl;
    if (best_score >= score) return;

    map<int, vector<int>> m;
    REP(n,N) {
        m[As[n][idx[n]]].pb(n);
    }

    int largest_m = 0;
    for(auto p: m) {
        largest_m = max(largest_m, SIZE(p.second));
    }
    if(largest_m == 1) return;

    for(auto p: m) {
        if (SIZE(p.second) == largest_m) {
            auto idx2 = idx;
            auto taken2 = taken;
            taken2.insert(p.first);

            if (taken_seen.count(taken2)) continue;
            taken_seen.insert(taken2);

            // cout << "taken: ";
            // for(auto zz: taken) cout << zz << " ";
            // cout << ". now " << p.first << " is taken" << endl;

            for(auto person: p.second) {
                while(taken2.count(As[person][idx2[person]])) {
                    ++idx2[person];
                }
            }
            dfs(idx2, As, taken2);
            break;
        }
    }
}

int main(void)
{
    cin.sync_with_stdio(false);
    cin >> N >> M;
    vector<vector<int>> As(N, vector<int>(M));
    REP(n,N) REP(m,M) cin >> As[n][m];


    vector<int> idx(N);
    set<int> taken;
    dfs(idx, As, taken);

    cout << score << endl;

    return 0;
}


Measured memory_bytes: 6272
#include <stdio.h>

int main(){
	
	int n, k;
	scanf("%d %d", &n, &k);
	
	long long int input[n];
	for(int i = 0; i < n; i++){
		scanf("%lld", &input[i]);
	}
	
	for(int i = 0; i < n-k; i++){
		if(input[i] < input[i+k]){
			puts("Yes");
		} else {
			puts("No");
		}
	}
	return 0;
}



Measured memory_bytes: 4704
#include <bits/stdc++.h>
#define FOR(i, a, n) for(int (i) = (int)(a); (i) < (int)(n); ++(i))
#define FORe(i, a, n) for(int (i) = (int)(a); (i) <= (int)(n); ++(i))
#define rFOR(i, a, n) for(int (i) = (int)(n)-1; (i) >= (int)(a); --(i))
#define rFORe(i, a, n) for(int (i) = (int)(n); (i) >= (int)(a); --(i))
#define REP(i, n) FOR((i), 0, (n))
#define REPe(i, n) FORe((i), 1, (n))
#define REPo(i, n) FORe((i), 0, (n))
#define rREP(i, n) rFOR((i), 0, (n))
#define rREPe(i, n) rFORe((i), 1, (n))
#define rREPo(i, n) rFORe((i), 0, (n))
#define rep(i, n) FOR((i), 0, (n))
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second
#define dup(x, y) (((x)+(y)-1)/(y))
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
using ll = long long;
using P = pair<int,int>;
using T = tuple<int,int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vs = vector<string>;
using vp = vector<P>;
using vt = vector<T>;

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

int main() {
  int n;
  cin >> n;
  map<string, int> st;
  REP(i, n) {
    string s;
    cin >> s;
    st[s]++;
  }
  cout << st.size() << endl;

  return 0;
}

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

int main(){
    double w,h,x,y;cin >>w>>h>>x>>y;
    
    cout << w*h/2 << " ";
    if(x*2==w && y*2==h)
      cout << 1 << endl;
    else
      cout << 0 << endl;
    return 0;
}


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

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll x;
	cin >> x;
	for (ll i=-1000; i<=1000; i++) {
		for (ll j=-1000; j<=1000; j++) {
			ll val1 = i*i*i*i*i;
			ll val2 = j*j*j*j*j;
			if (val1-val2==x) {
				cout << i << ' ' << j;
				return 0;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 3620
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
const int mod = (int)1e9 + 7;
int sum(int a, int b) {
    int s = a + b;
    if (s >= mod) s -= mod;
    return s;
}
int mult(int a, int b) {
    return (1LL * a * b) % mod;
}
int n, k;
const int maxN = 55;
int dp[maxN][maxN * maxN][maxN];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("input.txt", "r", stdin);
    cin >> n >> k;
    dp[0][0][0] = 1;
    for (int i = 0; i + 1 <= n; i++) {
        for (int k = 0; k <= i * i; k++) {
            for (int cur = 0; cur <= i; cur++) {
                dp[i + 1][k + 2 * cur][cur] = sum(dp[i + 1][k + 2 * cur][cur], dp[i][k][cur]);
                dp[i + 1][k + 2 * cur][cur + 1] = sum(dp[i + 1][k + 2 * cur][cur + 1], dp[i][k][cur]);
                if (cur) {
                    dp[i + 1][k + 2 * cur][cur - 1] = sum(dp[i + 1][k + 2 * cur][cur - 1], mult(mult(cur, cur), dp[i][k][cur]));
                    dp[i + 1][k + 2 * cur][cur] = sum(dp[i + 1][k + 2 * cur][cur], mult(mult(2, cur), dp[i][k][cur]));
                }
            }
        }
    }
    cout << dp[n][k][0];
    return 0;
}

Measured memory_bytes: 33024
a, b = map(int, input().split())
s = input()
if len(s) == a + b + 1 and s[a] == '-':
    for i in range(len(s)):
        if i != a and not ('0' <= s[i] and s[i] <= '9'):
            print('No')
            exit()
    print('Yes')
else:
    print('No')

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

int main() {
	string str;

	getline(cin, str);

	for(int i=0; i<str.size(); i++) {
		if(isupper(str[i]))
			str[i] += 'a'-'A';
		else if(islower(str[i]))
			str[i] += 'A'-'a';
	}

	cout << str << endl;
	return 0;
}


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

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

  int n;
  cin >> n;
  vector<int> l;
  for(int i = 0; i < n; i++) {
    int a;
    cin >> a;
    l.push_back(a);
  }

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

  int sum = 0;
  for(int i = 0; i < n-1; i++) sum += l[i];

  if(l[n-1] < sum) cout << "Yes" << endl;
  else cout << "No" << endl;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define eb emplace_back
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 2e5 + 233;
vector<int> a;
int n;
char s[1000];
int ans[1000];
int query(){
	printf("?");
	for(int x:a)printf(" %d",x);
	puts("");fflush(stdout);
	scanf("%s",s);
	if(s[0]=='R')return 0;
	return 1;
}
int check(int l){
	for(int i=0;i<n;i++){
		if(i<l)a[i] = i+1+n;
		else a[i] = i+1;
	}
	return query();
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)a.pb(i);
	int org =  query(),cur = org;
	int l = 0, r = n-1;
	while(l!=r){
		int mid = (l+r)>>1;mid++;
		if(check(mid)==org)l = mid;
		else r = mid-1;
	}
	for(int i=0;i<n;i++){
		if(i<l)a[i] = i+1+n;
		else a[i] = i+1;
	}
//	cout<<"!"<<l<<endl;
	ans[l+1] = org;ans[l+1+n] = org^1;
	for(int i=1;i<=n;i++){
		if(i<l+1){
			a[l] = i;
			ans[i] = query();
		}
		if(i>l+1){
			a[l] = i+n;
			ans[i+n] = query();
		}
	}
	for(int i=0;i<n;i++){
		if(i<l)a[i] = i+1;
		else a[i] = i+1+n;
	}
	for(int i=1;i<=n;i++){
		if(i<l+1){
			a[l] = i+n;
			ans[i+n] = query();
		}
		if(i>l+1){
			a[l] = i;
			ans[i] = query();
		}
	}
	printf("! ");
	for(int i=1;i<=2*n;i++){
		if(ans[i]==0)printf("R");
		else printf("B");
	}
	puts("");fflush(stdout);
}


Measured memory_bytes: 724
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>
#include <cmath>
#include <cassert>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)

void dfs ( int n, int m, int now, vector<int> tmp_num, vector<vector<int>> &num ) {
    if ( n == now ) {
        num.push_back(tmp_num);
        return;
    }
    //cout << "test" << " " << now << endl;
    if ( tmp_num.empty() ) {
        for ( int i = 1; i <= m; ++i ) {
            auto next = tmp_num;
            next.push_back(i);
            dfs(n, m, now+1, next, num);
        }
        return;
    }
    //for ( auto p : tmp_num ) {
    //    cout << p << " " ;
    //}
    //cout << endl;
    int size = (int)tmp_num.size();
    //cout << size - 1 << endl;
    for ( int i = tmp_num[size-1]; i <= m; ++i ) {
        auto next = tmp_num;
        next.push_back(i);
        dfs(n, m , now+1, next, num);
    }
    return;
}

int main(){
    int n, m, q;
    cin >> n >> m >> q;
    int ans = 0;
    vector<int> a(q);
    vector<int> b(q);
    vector<int> c(q);
    vector<int> d(q);
    rep(i, q) {
        int tmp_a, tmp_b;
        cin >> tmp_a >> tmp_b >> c[i] >> d[i];
        --tmp_a, --tmp_b;
        a[i] = tmp_a;
        b[i] = tmp_b;
    }
    vector<vector<int>> num;
    vector<int> tmp_num;
    dfs(n, m, 0, tmp_num, num);
    //cout << "test2" << endl;
    //for ( auto v : num ) {
    //    for ( auto p : v ) {
    //        cout << p << " ";
    //    }
    //    cout << endl;
    //}
    for ( auto v : num ) {
        //for ( auto p : v ) {
        //    cout << p << " ";
        //}
        //cout << endl;
        int sum = 0;
        rep(i, q) {
            //cout << v[b[i]] << " " << v[a[i]] << " " << c[i] << endl;
            if ( v[b[i]] - v[a[i]] == c[i] ) sum += d[i];
        }
        //cout << sum << endl;
        ans = max(ans, sum);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 9788
program atcoder
    implicit none
    integer(8) :: i,j,n,k,modd
    integer(8),allocatable,dimension(:,:) :: dp
    integer(8),allocatable,dimension(:) :: a
    read*,n,k
    allocate(dp(0:n,0:k))
    allocate(a(0:n))
    read(*,*)(a(i),i=1,n)
    modd = 1000000007
    do i = 0,n
        dp(i,0) = 1
    enddo
    do i = 1,n
        do j = 1,k
            if(j-a(i)-1 >= 0 ) then
                dp(i,j) = dp(i,j-1)+dp(i-1,j)-dp(i-1,j-a(i)-1)
            else
                dp(i,j) = dp(i,j-1)+dp(i-1,j)
            end if
            dp(i,j) = mod(mod(dp(i,j),modd)+modd,modd)
        enddo
    enddo
    write(*,'(I0)')dp(n,k)
    stop 
!---------------------------------------
contains

end program atcoder


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

#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()

int main() {
    int N; cin >> N;
    vector<int64_t> A(N);
    REP(i, N) cin >> A[i];

    vector<pair<int64_t, int>> indexed(N);
    REP(i, N) indexed[i] = {A[i], i};
    sort(ALL(indexed), greater<pair<int64_t, int>>());

    // dp[L][R] = 左にL人、右にR人配置したときの嬉しさの最大値
    vector<vector<int64_t>> dp(N+1, vector<int64_t>(N+1));
    REP(L, N+1) REP(R, N-L+1) {
        if (L == 0 && R == 0) {
            dp[L][R] = 0;
        } else {
            auto [_, k] = indexed[L+R-1];
            int64_t vl = L >= 1 ? dp[L-1][R] + A[k] * abs(k+1 - L)
                                : numeric_limits<int64_t>::min();
            int64_t vr = R >= 1 ? dp[L][R-1] + A[k] * abs(k+1 - (N-R+1))
                                : numeric_limits<int64_t>::min();
            dp[L][R] = max(vl, vr);
        }
    }

    int64_t ans = numeric_limits<int64_t>::min();
    REP(L, N+1) ans = max(ans, dp[L][N-L]);
    cout << ans << '\n';
}


Measured memory_bytes: 34652
import sys
from operator import itemgetter
def dhondt(Votes, n_seats):
    # ドント方式  候補者数 N に対して O(NlogN)
    n_candidates = len(Votes)
    sum_votes = sum(Votes)
    S0 = []  # 端数切り捨てによってすぐ確定できる席数
    C = []
    for i, v in enumerate(Votes):
        s0 = n_seats*v//sum_votes
        S0.append(s0)
        for s in range(s0+1, s0+10000):
            if s*sum_votes >= v*(n_seats+n_candidates):
                break
            C.append((s/v, i))
        else:
            assert False
    C.sort(key=itemgetter(0))
    S = S0[:]
    for _, i in C[:n_seats-sum(S0)]:
        S[i] += 1
    return S0, S


input = sys.stdin.buffer.readline
N, K = map(int, input().split())
A = list(map(int, input().split()))
sum_A = sum(A)
S0, S = dhondt(A, K)
ans = 0
for s, a in zip(S, A):
    ans = max(ans, -(-a//(s+1)))
print(ans)


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

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

int snuke[105];

int main() {
    int n, k; cin >> n >> k;
    vector<vector<int> > A(k);
    rep(i,k){
        int d; cin >> d;
        A[i].resize(d);
        rep(j,d){
            cin >> A[i][j];
            snuke[A[i][j]-1]++;
        }
    }
    int ans = 0;
    rep(i,n){
        if(snuke[i] == 0) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
int64_t q;
static const int64_t mod=1000003;
int64_t f(int64_t x,int64_t y){
if(y==0)
  return 1;
  else if(y%2==0)
    return (f(x,y/2)*f(x,y/2))%mod;
  else
    return (x*((f(x,y/2)*f(x,y/2))%mod))%mod;
}
int64_t A[mod];
int main(){
  int64_t a=1;A[0]=1;
  for(int64_t i=1;i<mod;i++){
  a=(a*i)%mod;A[i]=a;
  }
  cin>>q;
  for(int i=0;i<q;i++){
  int64_t x,d,n;cin>>x>>d>>n;
    if(x==0 && mod<=n)
      cout<<0<<endl;
    else if(d==0)
      cout<<f(x,n)<<endl;
    else{
    int64_t X=(x*f(d,mod-2))%mod;
      int64_t Y=X+n-1;
      if(mod<=Y)
        cout<<0<<endl;
      else{
      int64_t ans=(A[Y]*f(A[X-1],mod-2))%mod;
        ans=(ans*f(d,n))%mod;
        cout<<ans<<endl;
      }
         }
    }
  return 0;
}

Measured memory_bytes: 11440
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define ll long long
#define ld long double
#define mk make_pair
#define fi first
#define se second
#define vll vector<ll>
#define pii pair<ll,ll>
#define vvll vector< vector<ll> >
#define pb push_back
#define sz(v) (v).size()
#define inf 1e18
#define md 1000000007
#define all(v) (v).begin(),(v).end()
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define tel(a){cout<<a<<"\n";}
#define tell(a,b){cout<<a<<" | "<<b<<"\n";}
#define telll(a,b,c){cout<<a<<" | "<<b<<" | "<<c<<"\n";}
#define teln(v,n){cout<<"v- ";rep(i,0,n)cout<<v[i]<<" ";cout<<"\n";}
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using o_set=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define M 1000010

int main(){
	IOS;
	ll n,x;cin>>n>>x;
	ll a[n];rep(i,0,n)cin>>a[i];
	ll d[n+1];d[0]=0;
	ll ans=0;
	rep(i,1,n+1)d[i]=d[i-1]+a[i-1];
	rep(i,0,n+1)if(d[i]<=x)ans++;
	cout<<ans;
	return 0;
}



Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cassert>
#include <bitset>

//#include <boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;

//std::cout << std::fixed << std::setprecision(10)
//std::ios::sync_with_stdio(false);
constexpr long long MOD = 1000000007;

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

constexpr long long MAX = 200000 + 1;

long long fact[MAX], fact_inv[MAX];

long long power(long long a, long long b) {
  long long res = 1;
  while (b > 0) {
    if (b & 1)
      res = res * a % MOD;
    a = a * a % MOD;
    b >>= 1;
  }
  return res;
}

long long comb(long long n, long long k)
{
  long long num = 1;
  for(long long i = 0; i < k; ++i)
    num = (num * (n-i)) % MOD;
  return (num*fact_inv[k]) % MOD;
}

int main()
{
  long long n, a, b;
  std::cin >> n >> a >> b;

  fact[0] = 1;
  for (int i = 0; i < b; ++i)
    fact[i + 1] = fact[i] * (i + 1) % MOD;
  fact_inv[b] = power(fact[b], MOD - 2);

  for (int i = b - 1; 0 <= i; --i)
    fact_inv[i] = fact_inv[i + 1] * (i + 1) % MOD;

  long long ans = power(2LL, n) - 1;
  if(ans < 0)
    ans = MOD - 1;
  ans = ans - comb(n, a);
  if(ans < 0)
    ans = (MOD - std::abs(ans)%MOD)%MOD;
  ans = ans - comb(n, b);
  if(ans < 0)
    ans = (MOD - std::abs(ans)%MOD)%MOD;
  std::cout << ans << std::endl;

  return 0;
}



Measured memory_bytes: 3328
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    int K = sc.nextInt();
    HashSet<String> S = new HashSet<>();
    for (int i = 0; i < s.length(); i++) {
      for (int j = i + 1; j <= s.length(); j++) {
        if (j - i > K) {
          break;
        }
        S.add(s.substring(i, j));
      }
    }
    ArrayList<String> T = new ArrayList<>(S);
    Collections.sort(T);
    System.out.println(T.get(K - 1));
  }
}


Measured memory_bytes: 26960
# -*- coding: utf-8 -*-
#import pprint
import re
import sys


N,M = list(map(int, input().rstrip().split()))
A_list = [input().strip() for _ in range(N)]
B_list = [input().strip() for _ in range(M)]

#print("N,M",N,M)
#print("A_list",A_list)
#print("B_list",B_list)
#-----

candidate=[]   # [[x,y]] start position of row(x) and column(y) 
for ia in range(N):
    #find_string = A_list[ia].find( B_list[0] )
    find_string = [m.start() for m in re.finditer( B_list[0] , A_list[ia])]
    
    
    #if find_string != -1 and N-ia >= M:
    if find_string != [] and N-ia >= M:
        candidate.append( [ia,find_string] )

#print("candidate",candidate)

if candidate == []:
    print("No")
    #print("---No candidate")
    sys.exit()

check_column=""
#for start_r,start_c in candidate:
for start_r,start_c_list in candidate:
    for start_c in start_c_list:
    
        for ib in range(M):
            #print("start_r",start_r,"start_c",start_c,"ib",ib,"B_list",B_list[ib],"A_list",A_list[start_r + ib][start_c:(start_c + M)])

            #find_string = A_list[start_r + ib].find( B_list[ib] )
            if B_list[ib] ==  A_list[start_r + ib][start_c:(start_c + M)]:
                if ib == (M-1):
                    print("Yes")
                    sys.exit()
                else:
                    continue
            else:
                #print("break")
                break

else:
    print("No")


Measured memory_bytes: 3188
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;

int main(){
	int a,b,c,d; cin >> a >> b >> c >> d;
	while(a > 0 && c > 0){
		c-=b;
		if(c <= 0) {
			cout << "Yes" << endl;
			break;
		}
		a-=d;
		if(a <= 0) {
			cout << "No" << endl;
			break;
		}
	}

	return 0;
}

Measured memory_bytes: 3584
#include<bits/stdc++.h>
using namespace std;
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define SZ(x) ((int)(x).size())
#define debug(x) cerr << #x << ": " << x << '\n'
#define INF 999999999
typedef long long int Int;
typedef pair<int,int> P;
using ll = long long;
using VI = vector<int>;
int main(){
  int a,b,c;cin >> a >> b >> c;
  cout << (c>=a&&c<=b?"Yes":"No") << endl;
  return 0;
}


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



int main() {
	string S;
	int a = 0;
	cin >> S;
	int b = 0;
	b = S[1];
	if (S[0] != 'A' || S[1] == 'C' || S[S.size() - 1] == 'C'||b<97) {
		cout << "WA";
		return 0;
	}
	else {
		for (int i = 1; i < S.size(); i++) {
			if (S[i] == 'C') {
				a++;
			}
			b = S[i];
			
			if (b < 97 && b != 67) {
				cout << "WA";
				return 0;
			}
			
		}
		if (a == 1) {
			cout << "AC";
		}
		else {
			cout << "WA";
		}
	}

}

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
string s, t;
int main(){
    cin >> s >> t;
    int mn = t.size();
    for(int i = 0 ; i < s.size() - t.size() + 1; i++){
        string temp = s.substr(i, t.size());
        int cnt = 0;
        for(int i = 0 ; i < t.size() ; i++)
            if(temp[i] != t[i])cnt++;
        mn = min(mn, cnt);
    }
    cout << mn << endl;
    return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using  namespace  std;
using ll=long long;
int main(){
  int a,b;
  cin>>a>>b;
  vector<int> s={0,1,2,1,3,1,3,1,1,3,1,3,1};
  cout<<(s.at(a)==s.at(b)?"Yes":"No")<<endl;
}

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

typedef long long ll;
int mod = 1e9 + 7;

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	vector<int> b(n);
	vector<int> c(n - 1);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		a[i]--;
	}
	for (int i = 0; i < n; ++i) {
		cin >> b[i];
	}
	for (int i = 0; i < n - 1; ++i) {
		cin >> c[i];
	}
	int sum = b[a[0]];
	int p = a[0];
	for (int i = 1; i < n; ++i) {
		if (a[i] - 1 == p) {
			//cout << p << endl;
			sum += (a[i] - 1 >= 0) ? c[a[i] - 1] : 0;
		}
		sum += b[a[i]];
		p = a[i];
	}	
	cout << sum;
}



















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

ll gcd (ll x, ll y) { return y ? gcd(y,x%y) : x; }

ll lcm (ll x, ll y) { return x*y / gcd(x,y); }
 
int main() {
    ll a, b;
    cin >> a >> b;
    ll ans = lcm(a,b);
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using Graph = vector<vector<pii>>;
const int INF = 1e9 + 1;
const ll LLINF = 1e18;
const int MOD = 1e9 + 7;

int main() {
    int A, B;
    cin >> A >> B;
    for (int i = 1; i <= 3; ++i)
        if (i != A && i != B)
            cout << i << endl;
    return 0;
}


Measured memory_bytes: 256
//g++ -std=c++14 test.cpp -o test.out
 
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <map> 
#include <utility>
#include <limits.h>
#include <bitset>
#include <set>
using namespace std;
 
#define LL long long int
const LL INF = (LL)(1e18)+1;
const int INF_INT = 2147483647-1e6-1;
const LL mod = 1000000007ll;
const int mod_int = 1000000007;
 
string S;
 
int ans = 0;
 
void solve(){
	//まずSからxを抜いたものを考え、
	string S_without_x = "";
	for(int i=0;i<S.size();i++){
		if(S[i]!='x') S_without_x += S[i];
	}
	int N = S_without_x.size();
	if(N==0) return;
	//それが回文なのかを判定
	for(int i=0;i<N/2;i++){
		if(S_without_x[i]!=S_without_x[N-1-i]){
			ans = -1;
			return;
		}
	}
	//回文であれば以下を実行
	//xなしのSの一番真ん中の文字
	//が、Sにおいてはどのインデックスに位置するのかを
	//S_middle_indexに保管
	int S_middle_index = 0;
	for(int i=0;i<=N/2;i++){
		while(S[S_middle_index]=='x') S_middle_index++;
		S_middle_index++;
	}
	S_middle_index--;
	//cout << S_middle_index << " " << S[S_middle_index] << endl;
	//return;
	vector<int> x_num;
	int x_seq = 0;//連続するxの数
	for(int i=0;;i++){
		if(S[i]=='x'){
			x_seq++;
		}else{
			x_num.push_back(x_seq);
			x_seq = 0;
		}
		if(i==S_middle_index) break;
	}

	x_seq = 0;
	int x_num_index = 0;
	for(int i=S.size()-1;;i--){
		if(S[i]=='x'){
			x_seq++;
		}else{
			ans += abs(x_num[x_num_index]-x_seq);
			x_seq = 0;
			x_num_index++;
		}
		if(i==S_middle_index) break;
	}
}
 
int main(){
    cin >> S;
 
    solve();
 
    cout << ans << endl;
    return 0;
}

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

#if MYDEBUG
#include "lib/cp_debug.hpp"
#else
#define DBG(...) ;
#endif
#if __cplusplus <= 201402L
template <typename T>
T gcd(T a, T b) { return ((a % b == 0) ? b : gcd(b, a % b)); }
template <typename T>
T lcm(T a, T b) { return a / gcd(a, b) * b; }
#endif
using LL = long long;
constexpr LL LINF = 334ll << 53;
constexpr int INF = 15 << 26;
constexpr LL MOD = 1E9 + 7;

namespace Problem {
using namespace std;

class Solver2 {
 public:
  LL n, maxw;
  vector<LL> v, w;
  vector<vector<LL>> dp;
  Solver2(LL n, LL maxw) : n(n), maxw(maxw), v(n + 1), w(n + 1), dp(n + 1, vector<LL>(maxw + 1)){};

  void solve() {
    for (int i = 1; i <= n; ++i) {
      cin >> w[i] >> v[i];
    }
    for (int i = 1; i <= n; ++i) {
      for (int weight = 0; weight < w[i]; ++weight) {
        dp[i][weight] = dp[i - 1][weight];
      }
      for (int weight = w[i]; weight <= maxw; ++weight) {
        dp[i][weight] = max(dp[i - 1][weight], dp[i - 1][weight - w[i]] + v[i]);
      }
    }
    cout << *max_element(dp[n].begin(), dp[n].end()) << endl;
  }
};
}  // namespace Problem

int main() {
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(false);
  // std::cout << std::fixed << std::setprecision(12);
  long long n = 0, w;
  std::cin >> n >> w;

  Problem::Solver2 sol(n, w);
  sol.solve();
  return 0;
}


Measured memory_bytes: 80256
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) Rep(i, 0, n)
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;
//const int mod = 998244353;

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

    int n;
    cin >> n;
    vector<int> a(n), b(n);
    rep(i, n) cin >> a[i];
    rep(i, n) cin >> b[i];
    rep(i, n - 1) a[i + 1] += a[i];
    for (int i = n - 2; i >= 0; i--)
        b[i] += b[i + 1];
    int ans = -1;
    rep(i, n) ans = max(ans, a[i] + b[i]);
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mod 1000000007
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define nyan "(=^･ω･^=)"
#define mkp make_pair
typedef long long ll;
using namespace std;

int N, M, l, r, res[100002];

int main() {
	cin >> N >> M;
	for (int i = 0; i != N; ++i) {
		cin >> l >> r;
		int p;
		for (p = 1; p <= 400; ++p) {
			if ((l - 1) / p != r / p) {
				++res[p];
				--res[p + 1];
			}
		}
        --p;
		for (int j = 300; j; --j) {
			++res[max((l - 1) / j, p) + 1];
			p = max(r / j, p);
			--res[p + 1];
		}
	}
	for (int i = 1; i <= M; ++i) {
		res[i] += res[i - 1];
		cout << res[i] << endl;
	}
	return 0;
}


Measured memory_bytes: 1280
// abc130c.cpp : Rectangle Cutting
#include <bits/stdc++.h>
using namespace std;
#define otf(f,x) printf(f,x)

int main(){
	int w,h,x,y;cin>>w>>h>>x>>y;
	// (x,y) と 四角の中心を通る線が分割線
	// 四角の半分の面積が解になる
	otf("%f ",(double)w*h/2);
	// (x,y)=(w/2,h/2)=中心 なら複数ある
	otf("%d\n",w==x*2 && h==y*2);
}

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

using namespace std;

int main() {
  cin.tie(0);
  cin.sync_with_stdio(0);

  int n, k; cin >> n >> k;
  int h[n];
  for(int i = 0; i<n; ++i) cin >> h[i];

  vector<int> dp(n, INT_MAX);
  dp[0] = 0;
  for(int i = 0; i<n; ++i) {
    for(int j = 1; j<=k && i+j<n; ++j) {
      dp[i+j] = min(dp[i+j], dp[i]+abs(h[i] - h[i+j]));
    }
  }
  cout << dp[n-1] << endl;
}


Measured memory_bytes: 1024
function main(){
 
var seats = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];
var groupMembers = [2,5,2,2,2];
var eatTimes = [19,39,25,36,22,42];
 
var headGroup = -1;
var pastMinutes = 0;
var waitTime = [];
 
while(waitTime.length < 100){
  // たべおわる
  var slen = seats.length;
  for(; slen--;){
    seats[slen] = mx(seats[slen] - 1, 0);
  }
 
  // 来店
  if(headGroup == -1 && pastMinutes % 5 == 0){
    headGroup = pastMinutes / 5;
  }
 
  // ちゃくせき
  while(headGroup != -1){
    var needsSequencialSeats = groupMembers[headGroup % 5];
    var sequencialSeats = 0;
    var startIndex = -1;
    for(var i = 0, sl = seats.length; i < sl; i++){
      sequencialSeats = seats[i] == 0 ? sequencialSeats + 1 : 0;
 
      if(sequencialSeats == needsSequencialSeats){
        startIndex = i - (needsSequencialSeats - 1);
        break;
      }
    }
 
    if(startIndex != -1){
      // すわれたみたい
      waitTime[headGroup] = pastMinutes - (headGroup * 5);
      for(var i = startIndex, total = (needsSequencialSeats + startIndex); i < total; i++){
        seats[i] = eatTimes[headGroup % 6];
      }
       
      headGroup = (((headGroup + 1) * 5) <= pastMinutes) ? headGroup + 1 : -1;
    }else{
      // すわれなかったみたい
      break;
    }
 
  }
 
  pastMinutes++;
 
}
 
for(var i = 0, ilen = (input.length - 1); i < ilen; i++){
  console.log(waitTime[parseInt(input[i], 10)]);
}
 
}

function mx(a, b){
 var t = (a-b);
 return a - (t & (t >> 31));
}
 
var
input = '';
 
process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data', function(chunk) {
  input += chunk;
});
process.stdin.on('end', function() {
  input = input.split('\n');
  main();
});

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

using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int x;
    cin >> x;
    double ans = 0;
    if (x == 2) {
        cout << "0.5000000000" << "\n";

    } else if (x % 2 == 0) {
        double bb = x / 2;
        ans = (bb / x);
        cout << fixed << setprecision(6) << ans << "\n";


    } else if (x % 2 != 0) {
        double aa = ((x / 2) + 1);
        ans = (aa / x);
        cout << fixed << setprecision(6) << ans << "\n";

    }

}















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

struct vals{
    int a;
    int b;
    int c;
    vals(int x, int y, int z)
        :a(0), b(0), c(0)
    {
        a=x;b=y;c=z;
    }
};

vals f(int n, vector<vector<int>> &v)
{
    vector<vals> dp(n+1, vals(0, 0, 0));
    dp[1]=vals(v[1][0], v[1][1], v[1][2]);
    
    for(int i=2; i<=n; i++)
        dp[i] = vals(max(dp[i-1].b, dp[i-1].c)+v[i][0], max(dp[i-1].a, dp[i-1].c)+v[i][1], max(dp[i-1].a, dp[i-1].b)+v[i][2]);
    return dp[n];
}


int main()
{
  int n;
  cin >> n;
  int numAct = 3;
  vector<vector<int>> v(n+1, vector<int>(numAct));
  for(int i=1; i<=n; i++)
    for(int j=0; j<3; j++)
      cin >> v[i][j];
    
  vals res = f(n, v);
  cout << max(res.a, max(res.b, res.c)) << endl;
}

Measured memory_bytes: 6912
object MainKt {
  
  @JvmStatic fun main(args:Array<String>) {
    val N=readLine()!!.toInt()
    val S=readLine()!!
    assert(S.length==N)
    var ins_front=""
   
    var correspond=0
    
    for(i in S.indices) {
      if(S[i]=='(') {
        correspond+=1
      }
      else {
        if(correspond==0) {
          ins_front+="("
        }
        else{
          correspond-=1
        }
      }
    }
     val ins_back=if(correspond==0) {""} else { (1..correspond).map{')'}.joinToString("")}
     println(ins_front+S+ins_back)
  }
}


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

int main() {
  string S;
  cin >> S;
  int ans = 0;
  for (int i = 0; i < 4; ++i) {
    if (S.at(i) == '+') {
      ++ans;
    } else {
      --ans;
    }
  }
  cout << ans << endl;
}


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

int main() {
  string s;
  cin >> s;
  bool a = false;
  if(s[0] == 'A') a = true;
  int r = 2; int l = s.size() - 2;
  int C = 0;
  int D = 0;
  for(int i = r;  i <= l; i++) 
    if(s[i] == 'C') C++;
  for(int i = 0; i < s.size(); i++) {
    if(s[i] >= 'a' && s[i] <= 'z') D++;
  }

  if(a && C == 1 && D == s.length() - 2){
    cout << "AC" << endl;
  }
  else cout << "WA" << endl;
  
}



Measured memory_bytes: 256
import java.util.Scanner
object Main extends App {
  val sc = new Scanner(System.in)
  val n = sc.nextInt
  val arr: Array[Map[Int, Boolean]] = Array.fill(n){
    Array.fill(sc.nextInt)(sc.nextInt - 1 -> (sc.nextInt == 1)).toMap
  }

  val valids = (1 until (1 << n)).map{ i =>
    val valid = (0 until n)
      .filter{j => ((1 << j) & i) != 0}
      .forall{j => arr(j).forall{case (k, b) => (((1 << k) & i) != 0) == b}
    }
    if (valid) Integer.bitCount(i) else 0
  }

  println(valids.max)
}

Measured memory_bytes: 41872
N,M = map(int,input().split())
X = sorted(list(map(int, input().split())))

#XX = [0 for _ in range(M+1)]
XX = []
for i in range(M):
    if i == 0:
#        XX[i] = 0
        continue
    else:
        XX.append((abs(X[i] - X[i-1]),i-1))

XX_sort = sorted(XX,reverse=True)
#XX_sort_1 = XX_sort[:N-1]
XX_sort_2 = XX_sort[N-1:]

if N >= M:
    ans = 0
elif N == 1:
    ans = abs(X[-1] - X[0])
else:
    ans = 0
    for k,v in XX_sort_2:
        ans += k

print(ans)


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

int main() {
  vector<int> alphabet(26, 0);
  while (true) {
    char ch;
    if (scanf("%c", &ch) == EOF) {
      break;
    }
    if (ch >= 'a' && ch <= 'z') {
      alphabet.at(ch - 'a')++;
    }
    else if (ch >= 'A' && ch <= 'Z') {
      alphabet.at(ch - 'A')++;
    }
  }
  rep(i, alphabet.size()) {
    cout << (char)('a' + i) << " : " << alphabet.at(i) << endl;
  }
}



Measured memory_bytes: 3144
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define all(c) c.begin(), c.end()
#define gmax(x,y) x=max(x,y)
#define gmin(x,y) x=min(x,y)
#define gadd(x,y) x=add(x,y)
#define gmul(x,y) x=mul(x,y)
using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
typedef vector<int> vi;

const int N = 1e5 + 5;
vi g[N];

int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	int n,m;
	cin >> n >> m;
	vi h(n);
	rep(i,0,n)cin >> h[i];
	rep(i,0,m){
		int x,y;
		cin >> x >> y;
		--x,--y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	int ans = 0;
	rep(i,0,n){
		bool val = true;
		for(int v:g[i]){
			if(h[v] >= h[i])val = false;
		}
		ans += val;
	}
	cout << ans << '\n';
}


Measured memory_bytes: 8724
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(int i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(int i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(int i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define uniq(x) (x).erase(unique((x).begin(), (x).end()), (x).end())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int l = 0, r = n;
    string zs;
    cout << 0 << endl;
    cin >> zs;
    if (zs == "Vacant") return 0;
    rep(i, 20) {
        int m = (l + r) / 2;
        string s;
        cout << m << endl;
        cin >> s;
        if (s == "Vacant") return 0;
        if ((m % 2) == 0) {
            if (zs != s) r = m;
            else l = m;
        }
        else {
            if (zs != s) l = m;
            else r = m;
        }
    }
    return 0;
}


Measured memory_bytes: 852
#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

int n,m,x,c[13];
int a[13][13];
int algo[13];


int ans= 2147483647;

void saiki(int k,int sum){

    if(k==n){
        for(int i=0;i<m;i++){
            if(algo[i]<x)return;
        }
        if(sum<ans){ans=sum;}
        return;
    }

    saiki(k+1,sum);

    for(int i=0;i<m;i++){
        algo[i]+=a[k][i];
    }
    saiki(k+1,sum+c[k]);
    for(int i=0;i<m;i++){
         algo[i]-=a[k][i];
    }
}

int main(){

    cin >> n >> m >> x;
    for(int i=0;i<n;i++){
        cin >> c[i];
        for(int j=0;j<m;j++)cin >> a[i][j];
    }
    
    saiki(0,0);

    if(ans == 2147483647){
        cout << "-1" << endl;
    }else{
       cout << ans << endl;
    }

    return 0;
}

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

#define mp make_pair
#define eb emplace_back
#define ff first
#define ss second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int MAXN = 100;
//#define int long long
const int INF = 1e9;

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

	int k;
	cin >> k;

	int cur = 7 % k;
	int ans = 1;

	for (int i = 0; i < 1e7; i++){
		if (!cur){
			cout << ans << '\n';
			return 0;
		}

		cur *= 10;
		cur += 7;
		cur %= k;
		ans++;
	}

	cout << "-1\n";
    return 0;
}


Measured memory_bytes: 3648
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <string>
#include <cmath>
#include <complex>
#include <numeric>
#include <cassert>

#include <vector>
#include <array>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <utility>

#define PI 3.14159265358979323846
#define int64 long long
#define uint64 unsigned long long
using namespace std;

int main()
{
	int64 nn, xx, ans = 0;
	cin >> nn >> xx;
	vector<int64> aa(nn);
	for(int64 ii = 0;ii < nn;ii++)
	{
		cin >> aa[ii];
	}
	if(aa[0] > xx)
	{
		ans += aa[0] - xx;
		aa[0] = xx;
	}
	for(int64 ii = 1;ii < nn;ii++)
	{
		if(aa[ii - 1] + aa[ii] > xx)
		{
			ans += aa[ii] + aa[ii - 1] - xx;
			aa[ii] = xx - aa[ii - 1];
		}
	}
	cout << ans << endl;
	return 0;
}

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

int main() {
	int n, d;
    scanf("%d %d", &n, &d);
	int result = 0;
	for (int i = 0; i < n; i++) {
		long long x, y;
        scanf("%lld %lld", &x, &y);
		if (x * x + y * y <= (long long)d * d)
			result++;
	}
    printf("%d\n", result);
}


Measured memory_bytes: 3780
#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll> > mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;
const int dx[9] = {-1, 0, 0, 1, -1, -1, 1, 1, 0};
const int dy[9] = {0, -1, 1, 0, -1, 1, -1, 1, 0};

int N, C;
int s, t, c;
int imos1[35][101010];
int imos2[101010];

signed main()
{
  cin >> N >> C;
  REP(i,N) {
    cin >> s >> t >> c;
    imos1[c][s]++;
    imos1[c][t+1]--;
  }
  REP(i,35) {
    bool one = false;
    for (int j=1; j<101010; j++) {
      imos1[i][j] += imos1[i][j-1];
      if (imos1[i][j] == 1 && !one) {
        imos2[j]++;
        one = true;
      } else if (imos1[i][j] == 0 && one) {
        imos2[j]--;
        one = false;
      }
    }
  }
  int ans = 0;
  for (int i=1; i<101010; i++) {
    imos2[i] += imos2[i-1];
    ans = max(ans, imos2[i]);
  }
  cout << ans << endl;
  //REP(i,20) cout << imos[i];
}

Measured memory_bytes: 28672