akhauriyash/Code-Regression huggingface dataset:
N, K = map(int, input().split())
p = list(map(int, input().split()))
D = [sum(p[0:K])]
if N-K >= 1:
  for i in range(1, N-K+1):
    D.append(D[-1] - p[i-1] + p[i+K-1])
#print(D)
print(max(D) / 2 + 0.5 * K)

Measured memory_bytes: 25060
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,ww;
    cin >> n >> ww;
    long w[n];
    long v[n];

    for(int i=0;i<n;i++)cin >> w[i] >> v[i];

    vector<long>dp(100001,1<<30);
    dp[0] = 0;

    for(int i=0;i<n;i++){
        for(int j=100000;j>=0;j--){
            if(j + v[i] <= 100000){
                dp[j+v[i]] = min(dp[j+v[i]],dp[j] + w[i]);
            }
        }
    }
    for(int i=100000;i>=0;i--){
        if(dp[i] <= ww){
            cout << i << endl;
            break;
        }
    }
}

Measured memory_bytes: 4048
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>

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

//prototype declaration
int getint();
long long getllint();
double getdint();
char getch();
void setstring(char *s);
void showint(int i);
void showllint(long long i);
void showdouble(double i);
void showchar(char c);
void showstring(char *s);

int myPower(int a, int n) { // aのn乗の計算
	int x = 1;
	while (n > 0) { // 全てのbitが捨てられるまで
		if ( n & 1) { // 一番右のbitが１のとき
			x *= a;
		}
		a *= a;
		n >>= 1; // bit全体を右に1つシフトして一番右を捨てる
	}
	return x;
}

int min(int a, int b) {
	return a < b ? a : b;
}

int main(void) {
	int a, p, i;
	a = getint();
	p = getint();
	p += a * 3;

	showint(p / 2);
	return 0;
}

int getint() {
	int i;
	scanf("%d", &i);
	return i;
}

long long getllint() {
	long long i;
	scanf("%lld", &i);
	return i;
}

double getdint() {
	double i;
	scanf("%lf", &i);
	return i;
}

char getch() {
	char c;
	scanf("%c", &c);
	return c;
}

void setstring(char *s) {
	scanf("%s", s);
}

void showint(int i) {
	printf("%d\n", i);
}

void showllint(long long i) {
	printf("%lld\n", i);
}

void showdouble(double i) {
	printf("%lf\n", i);
}

void showchar(char c) {
	printf("%c\n", c);
}

void showstring(char *s) {
	printf("%s\n", s);
}


Measured memory_bytes: 128
from collections import deque
def main():
    N,M,*AB=map(int,open(0).read().split())
    g=[[] for _ in range(N+1)]
    for a,b in zip(*[iter(AB)]*2):
        g[a].append(b)
        g[b].append(a)
    q=deque([1])
    s=[0]*(N+1)
    s[1]=1
    while q:
        u=q.popleft()
        for v in g[u]:
            if not s[v]:
                s[v] = u
                q.append(v)
    print("Yes")
    print("\n".join(map(str, s[2:])))
if __name__ == "__main__":
    main()

Measured memory_bytes: 56844
#!/usr/bin/env python3
import sys
import re


def solve(N: int, S: str):
    result = 0
    for s in set(S):
        regex = re.compile(s + "+")
        # print(regex.findall(S))
        result += len(regex.findall(S))
    print(result)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)


if __name__ == "__main__":
    main()


Measured memory_bytes: 4340
N, A, B, C, D = (int(x) for x in input().split())

if N%A==0:
    x = N//A
if N%A>0:
    x = (N//A)+1
if N%C==0:
    y = N//C
if N%C>0:
    y = (N//C)+1

if B*x<=D*y:
    print(B*x)
if D*y<B*x:
    print(D*y)


Measured memory_bytes: 5604
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <string>
#include <cmath>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>PP;
const ll MOD = 1000000007;
int T[200005]={0};
ll A[200005]={0};
ll C[200005]={0};
ll D[200005]={0};
ll B[2020]={0};

int main(){
  string S;cin>>S;
  for(int i=0;i<S.size();i++){
    T[i]=S[i]-'0';
  }
  ll n=S.size();
    A[n-1]=1;
  for(int i=n-2;i>=0;i--){
    A[i]=(A[i+1]*10)%2019;
  }
  //C[0]=(A[0]*T[0])%2019;
  for(int i=1;i<=n-1;i++){
    T[i]=(T[i-1]*10+T[i])%2019;
  }
  for(int i=0;i<=n-1;i++){
    C[i]=(A[i]*T[i])%2019;
  }

  for(int i=0;i<n;i++){
  //  cout<<C[i]<<" ";
    B[C[i]]++;
  }
  B[0]++;
//  cout<<endl;
  ll ans=0;
  for(int i=0;i<2019;i++){
    ans+=(B[i]*(B[i]-1))/2;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 7608
#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int main() {

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

        int dp[n+1][k+1];
        for(int i=0;i<=k;i++)
         dp[0][i]=0;

        dp[0][0]=1;
        for(int i=1;i<=n;i++)
        {
            int temp[k+1];
            temp[0]=dp[i-1][0];
            for(int j=1;j<=k;j++)
             temp[j]=(temp[j-1]+dp[i-1][j])%mod;
            for(int j=0;j<=k;j++) 
            {
                int sum=temp[j];
                int noti=j-arr[i]-1;
                if(noti>=0)
                 {sum=(sum-temp[noti]+mod)%mod;}
                // cout<<sum; 
                dp[i][j]=sum; 
            }
        } 
        cout<<dp[n][k];
}


Measured memory_bytes: 40064
#include<stdio.h>
#include<utility>
#include<vector>
using namespace std;
#define pii pair<int,int>
int H[100005];
main()
{
    int n,temp;
    scanf("%d",&n);
    vector<pii> V;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&temp);
        H[temp]++;
    }
    int counter = 0;
    for(int i=0;i<100002;i++)
    {
        if(H[i]>=1)
            counter++;
    }
    if(counter % 2 == 0)
        counter--;
    printf("%d",counter);
}


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

using namespace std;

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = long long;
using P = std::tuple<int,int>;

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

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

    string S;
    std::cin >> S;

    if(S.substr(0, 4) == "YAKI"){
        std::cout << "Yes" << std::endl;
    }else{
        std::cout << "No" << std::endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  auto fn = [&](const auto& fn, const string& s) -> int {
    if (s[1] != '[') {
      return stoi(s.substr(1, (int)s.size() - 2)) + 1 >> 1;
    }
    V<> v;
    for (int l = 1; l < (int)s.size() - 1; ) if (s[l] == '[') {
      int r = -1, t = 0;
      for (int i = l; ; ++i) {
        if (s[i] == '[') ++t;
        else if (s[i] == ']') --t;
        if (!t) {
          r = i;
          break;
        }
      }
      v.push_back(fn(fn, s.substr(l, r - l + 1)));
      l = r + 1;
    }
    sort(begin(v), end(v));
    int res = 0;
    for (int i = 0; i < (int)v.size() + 1 >> 1; ++i) res += v[i];
    return res;
  };
  int n; cin >> n;
  while (n--) {
    string s; cin >> s;
    cout << fn(fn, s) << '\n';
  }
}


Measured memory_bytes: 3260
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

#define NUM 999999999999999

struct Info{
	Info(int arg_dimension,ll arg_total_damage,int arg_pre_dimension){
		dimension = arg_dimension;
		total_damage = arg_total_damage;
		pre_dimension = arg_pre_dimension;
	}
	int dimension,pre_dimension;
	ll total_damage;
};

int main(){

	int N,M,start,goal;

	scanf("%d %d %d %d",&N,&M,&start,&goal);
	ll* damage = new ll[N+1];

	for(int i = 1; i <= N; i++){
		scanf("%lld",&damage[i]);
	}

	vector<int> V[N+1];

	int from,to;

	for(int loop = 0; loop < M; loop++){
		scanf("%d %d",&from,&to);
		V[from].push_back(to);
	}

	ll* min_damage = new ll[N+1];

	for(int i = 1; i <= N; i++){
		min_damage[i] = NUM;
	}

	queue<Info> Q;

	Q.push(Info(start,0,0));
	min_damage[start] = 0;

	while(!Q.empty()){

		if(Q.front().dimension == goal){
			Q.pop();
		}else if(Q.front().total_damage > min_damage[Q.front().dimension]){
			Q.pop();
		}else{

			if(Q.front().pre_dimension > Q.front().dimension){

				for(int i = 0; i < V[Q.front().dimension].size(); i++){
					if(V[Q.front().dimension][i] > Q.front().pre_dimension){ //????????°??????????????????????????´?????????????§?
 						if(min_damage[V[Q.front().dimension][i]] > Q.front().total_damage+damage[V[Q.front().dimension][i]]){
 							min_damage[V[Q.front().dimension][i]] = Q.front().total_damage+damage[V[Q.front().dimension][i]];
 							Q.push(Info(V[Q.front().dimension][i],min_damage[V[Q.front().dimension][i]],Q.front().pre_dimension));
 						}
					}
				}

			}else{

				for(int i = Q.front().pre_dimension+1; i <= Q.front().dimension-1;i++){
					if(min_damage[i] > Q.front().total_damage){
						min_damage[i] = Q.front().total_damage;
						Q.push(Info(i,Q.front().total_damage,Q.front().dimension));
					}
				}

				for(int i = 0; i < V[Q.front().dimension].size(); i++){
					if(min_damage[V[Q.front().dimension][i]] > Q.front().total_damage+damage[V[Q.front().dimension][i]]){
						min_damage[V[Q.front().dimension][i]] = Q.front().total_damage+damage[V[Q.front().dimension][i]];
						Q.push(Info(V[Q.front().dimension][i],min_damage[V[Q.front().dimension][i]],Q.front().dimension));
					}
				}
			}
			Q.pop();
		}
	}

	printf("%lld\n",min_damage[goal]);

	return 0;

}

Measured memory_bytes: 21108
N, M = [int(i) for i in input().split()]

def prime_decomposition(n):
  table = []
  i = 2
  while i * i <= n:
    count = 0
    while n % i == 0:
      n //= i
      count += 1
    if count != 0:
        table.append((i, count))
    i += 1
  if n > 1:
    table.append((n, 1))
  return table

def cmb(n, r):
    N, R = n, r
    for i in range(1, r):
        N *= n - i
        R *= r - i
    return N // R

mod = 10 ** 9 + 7
A = prime_decomposition(M)
result = 1
for _, a in A:
    result = result * cmb(a + N - 1, a) % mod

print(result)

Measured memory_bytes: 3064
#include <iostream>
#define MAX 1000000
using namespace std;

int main(){
  
   bool p[MAX];
   p[0] = p[1] = false;
   for(int i=2;i<MAX;i++)p[i] = true;
   for(int i=2;i<MAX;i++){
      if(p[i]){
	 for(int j=i+i;j<MAX;j=j+i){
	    p[j] = false;
	 }
      }
   }
   
   int n;
   while (cin >> n,n){
      int sum = 0;
      int num = 0;
      while(n){
	 if(p[num]) {
	    sum += num;
	    n--;
	 }
	 num ++;
      }
      cout << sum << endl;
   }

  return 0;
}

Measured memory_bytes: 2132
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
int main() {
    // 3^45 mod. 1000000007 を計算してみる
    //cout << modpow(3, 45, 1000000007) << endl;	
    ll n;
    cin>>n;
    ll cnt1=modpow(10,n,inf);
    ll cnt2=modpow(9,n,inf);
    ll cnt3=modpow(8,n,inf);
    ll fa=2*cnt2;
    fa%=inf;
    fa-=cnt3;
    if(fa<0){
    	fa+=inf;
    }
    fa=cnt1-fa;
    if(fa<0){
    	fa+=inf;
    }
    cout <<fa;
	// your code goes here
	return 0;
}

Measured memory_bytes: 3668
#include<iostream>
#include <bits/stdc++.h>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

int max(int a, int b ){
    if(a>=b) return a;
     return b ;
}

int main() {
	
    int a,b,c,k ;
    cin >> a >> b >> c >> k ;
    int MAX = max(max(a,b),c) ;
    int ans = a+b+c-MAX ;

    for(int i=1;i<=k;i++){
        MAX *= 2 ;
    }    
    cout << ans+MAX << endl ;  
	return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;
typedef long long ll;
const int mod=1e9+7;
ll a[maxn],f[maxn];
int main()
{
	std::ios::sync_with_stdio(false);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		ll w;
		cin>>w;
		a[w]=1;
	}
	f[0]=1;
	if(!a[1])f[1]=1;
	else f[1]=0;
	for(int i=2;i<=n;i++)
	{
		if(!a[i])
		{
			f[i]=(f[i]+f[i-1])%mod;
			f[i]=(f[i]+f[i-2])%mod;
		}
	}
	cout<<f[n]%mod;
	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define LLINF 9223372036854775807
#define MOD ll(1e9+7)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cerr<<#x<<": "<<x<<endl

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

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

    vector<ll> bit(62,0);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 62; j++){
            if((a[i]>>j)&1){
                bit[j]++;
            }
        }
    }
    ll ans = 0;
    for(int i = 0; i < 62; i++){
        ll t = (1LL<<i);
        t %= MOD;
        t *= bit[i];
        t %= MOD;
        t *= n-bit[i];
        t %= MOD;
        ans += t;
        ans %= MOD;
    }
    cout << ans%MOD << endl;

    return 0;

}


Measured memory_bytes: 2560
import java.util.*;
import java.io.*;

public class Main{
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    int n = scan.nextInt();
    int m = scan.nextInt();
    int x = scan.nextInt();
    int y = scan.nextInt();
    int x_max = 0;
    int y_min = 0;
    boolean flag = false;

    for(int i = 0; i < n; i++){
      int tmp = scan.nextInt();
      if(i == 0)  x_max = tmp;
      x_max = Math.max(x_max, tmp);
    }

    for(int i = 0; i < m; i++){
      int tmp = scan.nextInt();
      if(i == 0)  y_min = tmp;
      y_min = Math.min(y_min, tmp);
    }

    for(int z = x_max+1; z <= y_min; z++){
      if(x < z && z <=y){
        if(x_max < y_min){
          flag = true;
          break;
        }
      }
    }

    if(flag == true)
      System.out.println("No War");
    else
    System.out.println("War");

  }
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define bit(x) (1L << (x))
using ll = long long;
using namespace std;

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

int main() {
  constexpr ll mod = 1e9 + 7;
  int n; cin >> n;

  auto dp = make_v(n+1, map<string, ll>());

  auto ch = {"A", "T", "G", "C"};
  for(string x: ch)for(string y: ch)for(string z: ch){
    string t = x + y + z;
    if(t == "AGC" || t == "ACG" || t == "GAC") dp[3][t] = 0LL;
    else dp[3][t] = 1LL;
  }

  function<bool(string)> check = [](string s){
    int n = static_cast<int>(s.length());

    REP(i, n-1){
      string t = s;
      swap(t[i], t[i+1]);

      if(t.find("AGC") != string::npos) return false;
    }

    return s.find("AGC") == string::npos;
  };

  FOR(i, 3, n)for(const auto& p: dp[i]){
    string m = p.first; ll v = p.second;

    for(string t: {"A", "G", "C", "T"}){
      if(check(m + t)){
        string sub = m.substr(1, 2);
        (dp[i + 1][sub + t] += v) %= mod;
      }
    }
  }

  ll ans = 0LL;
  for(const auto& p: dp[n]) (ans += p.second) %= mod;

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 896
#include <stdio.h>
int main() {
    int i,x;
    int data[3000],data2[3000];
    for(i=0;i<3000;i++){
        scanf("%d %d", &data[i], &data2[i]);
        if(data[i]==0 && data2[i]==0) break;
    }
    
    for(i=0;i<3000;i++){
        if(data[i]==0 && data2[i]==0){
            break;
        }else {
            if(data[i]>data2[i]){
                x=data[i];
                data[i]=data2[i];
                data2[i]=x;
            }
        }
        
        printf("%d %d\n", data[i], data2[i]);
    }
    return 0;
}

Measured memory_bytes: 1756
using System;

namespace ProgramingLearning
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = Console.ReadLine();
            var t = Console.ReadLine();

            var ans = 0;
            for(int i = 0; i<s.Length; i++)
            {
                if(s[i] != t[i])
                {
                    ans++;
                }
            }
            Console.WriteLine(ans);
        }
    }
}

Measured memory_bytes: 27452
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#define ll long long
#define MOD_P 1000000007
using namespace std;

int main()
{
	int a, b;
	double amax, amin, bmax, bmin;

	cin >> a >> b;

	amin = a * 12.5;
	amax = amin + 12.5;
	bmin = b * 10.0;
	bmax = bmin + 10.0;

	if (amax <= bmin || bmax <= amin) {
		printf("%d", -1);
		return 0;
	}

	for (int i = (int)bmin; i < bmax; i++) {
		if (amin <= i) {
			printf("%d", i);
			break;
		}
	}

	return 0;
}

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

int main() {

    ll N;
    cin >> N;
    vl A(N);
    vl B(N);

    rep(i, N) cin >> A[i] >> B[i];

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    ll left, right;
    ll ans = 0;
    if (N%2 == 1) {
        left = A[(N-1)/2];
        right = B[(N-1)/2];
    }
    else {
        left = (A[N/2-1] + A[N/2]);
        right = (B[N/2-1] + B[N/2]);
    }

    cout << right - left + 1 << endl;

    return 0;
}


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

bool vowel(char c){
	return c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o';
}
bool musei(char c){
	return c == 'k' || c == 's' || c == 't' || c == 'h' || c == 'p';
}

bool soku(string s){
	return s.size() >= 2 && s[0] == s[1];
}

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

	string S;
	while(cin >> S, S != "#") {
		vector<string> s;
		string tmp;
		for(int i = 0; i < S.size(); i++) {
			char c = S[i];
			tmp += c;
			if(vowel(c) || c == '\'' || (c == 'n' && i != S.size() - 1 && !vowel(S[i + 1]) && S[i + 1] != '\'')) {
				s.push_back(tmp);
				tmp = "";
			}
		}
		if(tmp != "") s.push_back(tmp);

		int N = s.size();
		vector<int> m(N);
		vector<int> aps(N);
		for(int i = 0; i < N; i++) {
			m[i] = musei(s[i].front());
			if(s[i].back() == '\'') {
				aps[i] = 1;
				s[i].pop_back();
			}
		}

		vector<int> ans(N);
		for(int i = 0; i < N; i++) {
			if(i != 0 && ans[i - 1]) continue;
			char b = s[i].back();
			if(b == 'i' || b == 'u') {
				if(m[i] && (i == N - 1 || m[i + 1])) {
					ans[i] = 1;
				}
			}
			if(b == 'a' || b == 'o') {
				if(i == N - 1) continue;
				if(!m[i] || !m[i + 1]) continue;
				if(b != s[i + 1].back()) continue;
				if(soku(s[i + 1])) continue;
				ans[i] = 1;
			}
		}

		for(int i = 0; i < N; i++) {
			for(auto c : s[i]) {
				if(vowel(c) && ans[i]) cout << '(';
				cout << c;
				if(vowel(c) && ans[i]) cout << ')';
			}
			if(aps[i]) cout << '\'';
		}
		cout << endl;
	}
}

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

using namespace std;

constexpr int MOD = 1000000007;

using Long = long long;
template<typename T>
using V = vector<T>;
template<typename T>
using Vv = V<V<T>>;
using Vb = V<bool>;
using Vvb = V<Vb>;
using Vi = V<int>;
using Vvi = V<Vi>;
using Vl = V<Long>;
using Vvl = V<Vl>;
using Vd = V<double>;
using Vvd = V<Vd>;
using Vs = V<string>;

template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    for (auto& x : v) {
        is >> x;
    }
    return is;
}

template <typename First, typename Second>
istream& operator>>(istream& is, pair<First, Second>& v) {
    for (auto& x : v) {
        is >> v.first >> v.second;
    }
    return is;
}

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    for (const auto& x : v) {
        os << x << ' ';
    }
    return os;
}

// *** SOLUTION BEGIN ***

vector<int> f(int n) {
    if (n == 3) {
        return {2, 5, 63};
    }
    if (n == 4) {
        return {2, 5, 20, 63};
    }
    vector<int> a(n);
    a[0] = 2;
    int last3 = 1;
    int sum = 2;
    int x = 3;
    for (int i = 1; i < n - 1; ++i) {
        while (x % 2 != 0 && x % 3 != 0 && x % 5 != 0) {
            x++;
        }
        a[i] = x;
        sum += x;
        if (x % 3 == 0) {
            last3 = i;
        }
        x++;
    }
    int rem = (30 - sum % 30) % 30;
    while (rem % 2 != 0) {
        a[last3] += 3;
        sum += 3;
        rem = (30 - sum % 30) % 30;
    }
    a[n - 1] = 30000 - 30 + rem;
    return a;
}

void solve() {
//    for (int m = 5; m <= 20000; ++m) {
//        auto a = f(m);
//        assert(a[0] == 2 && a[1] == 3);
//        Long sum = 0;
//        for (int i = 0; i < m; ++i) {
//            sum += a[i];
//            assert(a[i] % 2 == 0 || a[i] % 3 == 0 || a[i] % 5 == 0);
//            if (i > 0) {
//                //assert(a[i - 1] < a[i]);
//            }
//            assert(a[i] <= 30000);
//        }
//        assert(sum % 30 == 0);
//    }


    int n;
    cin >> n;
    cout << f(n);
}

// *** SOLUTION END ***

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout.precision(10);
    cout << fixed;
    solve();
    return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
#include<cctype>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);i++)
#define all(v) (v).begin(),(v).end()
typedef long long int ll;
#define pi 3.1415926535897932384
#define E9 1000000000
#define eps 1e-4
#define pii pair<int,int>

int main(){
  int N, M; cin >> N >> M;

  vector<ll> dp(N+1,-1);
  dp[0]=1;
  int a[M]; 
  rep(i,M) {
    cin >> a[i];
    dp[a[i]] = 0;
  }

  int MOD = 1000000007;
  for (int i=1;i<=N;i++){
    if (dp[i]==0) continue;

    if (i==1) dp[i] = dp[i-1];
    else dp[i] = (dp[i-1] + dp[i-2])%MOD;
  }
  cout << dp[N] << endl;

  // cout << fixed << setprecision(10);
  
  return 0;
}


Measured memory_bytes: 4212
void main() {
	auto ip = readAs!(int[]), K = ip[0], N = ip[1];
	auto A = readAs!(int[]);
	int[] arr;
	foreach(i; 0..N-1) arr ~= A[i+1] - A[i];
	arr ~= (K - A[$-1]) + (A[0]);
	debug arr.writeln;
	(K - arr.reduce!max).writeln;
}

// ===================================

import std.stdio;
import std.string;
import std.functional;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}

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

void toScreen(int x, int t)
{
    for (int i=0; i<t; i++)
    {
        cout << x;
    }
}

int main()
{
    int a, b;
    cin >> a >> b;
    if (a == b)
    {
        toScreen(a, a);
    }
    else if(a > b)
    {
        toScreen(b, a);
    }
    else
    {
        toScreen(a, b);
    }
    return 0;
}

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

for i in range(n):
    if a[0]<a[i]:
        up=True
        nin=a[0]
        break
    elif a[0]>a[i]:
        up=False
        nin=a[i]
        break
    if i==n-1:
        print(1000)
        exit()

total=1000

for i in range(1,n-1):
    if up:
        if a[i-1]<=a[i] and a[i]>a[i+1]:
            total+=(total//nin)*(a[i]-nin)
            up=False
    else:
        if a[i-1]>=a[i] and a[i]<a[i+1]:
            nin=a[i]
            up=True
if nin<a[n-1]:
    total+=(total//nin)*(a[n-1]-nin)
print(total)

Measured memory_bytes: 9248
program ABC075A
    implicit none
    integer(8)::A,B,C
    read(5,*)A,B,C

    if(A==B)then
        print'(i0)',C
    else if(B==C)then
        print'(i0)',A
    else if(A==C)then
        print'(i0)',B
    end if
end program ABC075A

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define FORL(i,x) for(int i=head[x];i;i=nxt[i])
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define PB push_back
#define MP make_pair
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() {
  string s;
  cin >> s;

  if(s=="SUN") cout << 7 << endl;
  if(s=="MON") cout << 6 << endl;
  if(s=="TUE") cout << 5 << endl;
  if(s=="WED") cout << 4 << endl;
  if(s=="THU") cout << 3 << endl;
  if(s=="FRI") cout << 2 << endl;
  if(s=="SAT") cout << 1 << endl;





}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pp pair<pair<ll, ll>,pair<ll, ll>>
#define pll pair<ll,ll>
#define ppll pair<ll,pll>
#define pdd pair<double,double>
#define vii vector<int>
#define vll vector<ll>
#define mat vector<vector<ll>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define fi first
#define sc second
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (ll) (x).size()
#define pq priority_queue<ll>
#define pqg priority_queue<ll,vector<ll>,greater<ll>>
#define LB(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define UB(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
#define ERASE(v) sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end())
#define int ll
// #define ll int
using namespace std;
const ll INF = 1 << 29;
const ll LLINF = (1LL << 60LL);
const ll MOD = 1000000007;
const int MAX_V = 500;
// const ll mod = 998244353;
const ll MAX = 2100000;
const double pi = acos(-1);
const double eps = 1e-10;
ll dx[8] ={1,0,-1,0,1,-1,1,-1};
ll dy[8] ={0,1,0,-1,1,-1,-1,1};
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; }







void solve() {
    ll n;
    ll x[200010],y[200010];
    cin>>n;
    vll v,t;
    rep(i,n){
        cin>>x[i]>>y[i];
        v.pb(x[i]-y[i]);
        t.pb(x[i]+y[i]);
    }
    sort(all(v));
    sort(all(t));
    ll a = v[n-1]-v[0], b= t[n-1]-t[0];
    cout<<max(a,b)<<endl;


}




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


    ll t=1;
    
    // cin>>t;

    rep(i,t){
        solve(); 
    }

    return 0;
}


Measured memory_bytes: 9808
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cctype>
#define rep(i,a,b) for(int (i)=(a);i<(b);i++)
#define INF 1000000000
using namespace std;
bool debug=false;

int main(){
  long long n,T;
  long long t[200005];
  long long sum=0;
  cin>>n>>T;
  rep(i,0,n)cin>>t[i];
  int s=t[0],e=t[0]+T;
  for(int i=1;i<n;i++){
    if(s<t[i]&&t[i]<e){
      e=t[i]+T;
    }else{
      sum+=e-s;
      e=t[i]+T;s=t[i];
      //cout<<"sum:"<<sum<<" "<<s<<" "<<e<<"  i="<<i<<endl;
    }
    
  }
  sum+=e-s;
  cout<<sum<<endl;
  return 0;
}


Measured memory_bytes: 1792
while True:
 x, y, s = map(int,input().split())
 lst=[]
 if x==0 and y==0 and s==0:
   break
 for i in range(1, s):
   for j in range(1, s):
     if (i*(100+x)//100) + (j*(100+x)//100) == s:
       lst.append((i*(100+y)//100) + (j*(100+y)//100))
 print(max(lst))


Measured memory_bytes: 5604
require 'date'
loop do
  y1,m1,d1,y2,m2,d2 = gets.split.map(&:to_i)
  break if [y1,m1,d1,y2,m2,d2]==[-1]*6
  date1 = Date.new(y1,m1,d1)
  date2 = Date.new(y2,m2,d2)
  p (date2-date1).to_i
end

Measured memory_bytes: 24000
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    s=input()
    if s[0]=="9" or s[1]=="9":
        print("Yes")
    else:
        print("No")
main()

Measured memory_bytes: 3064
#include <iostream>
#define e 0.000000001
using namespace std;
int func(int,int,double,int);
int p,q,a,n;
double k;
 
int main(){
  while(1){
    cin>>p>>q>>a>>n;
    if(!p) break;
    k=1.0*p/q;
    cout<<func(0,1,0,1)<<endl;
  }
  return 0;
}
 
int func(int x,int w,double y,int I){
  int r=0;
  if(-e<=k-y&&k-y<=e) r++;
  if(x==n||y>k+e) return r;
  for(int i=I;w*i<=a;i++) r+=func(x+1,w*i,1.0/i+y,i);
  return r;
}

Measured memory_bytes: 1160
#include <iostream>
#include <map>
#include <queue>
#include <stack>
using namespace std;


int main()
{

    string S, T;
    int a, b;
    string U;
    cin >> S >> T;
    cin >> a >> b;
    cin >> U;
    map<string, int> Ball_Num;
    Ball_Num[S] = a;
    Ball_Num[T] = b;
    if (U == S)
    {
        Ball_Num[S] -= 1;
    }
    else
    {
        Ball_Num[T] -= 1;
    }
    cout << Ball_Num[S] << " " << Ball_Num[T];
    
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class AtCoderA
{
    static void Main()
    {
        var sc = new Scanner();

        int a = sc.NextInt();
        int b = sc.NextInt();

        bool ok = a % 3 == 0 || b % 3 == 0 || (a + b) % 3 == 0;

        string answer = ok ? "Possible" : "Impossible";

        Console.WriteLine(answer);
    }

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}

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

//#define int long long
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rep1(i,n) for(int i=1;i<=(int)(n);++i)
#define rep11(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define repm(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb(n) push_back(n)
#define mp make_pair
#define MOD 1002000007
#define INF LONG_LONG_MAX

int main(){
    int h,a,br;
    cin>> h>>a;
    if ((h%a==0) ? br=h/a : br=(h/a)+1); 
    cout<< br <<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <queue>
#define ll long long
#define N 10000
#define mod 1000000007
#define LL 100
using namespace std;

int main(){
    ll a,b,c,k;
    cin>>a>>b>>c>>k;
    if (k<=a) cout<<k<<endl;
    else if (k<=a+b) cout<<a<<endl;
    else{
        ll p=k-a-b;
        cout<<a-p<<endl;
    }
}

Measured memory_bytes: 3652
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <array>
#include <vector>
#include <utility>
#include <bitset>
#include <queue>

using namespace std;

typedef long long ll;

constexpr ll INF = 1e18;

ll f(ll b, ll n) {
    if (n < b) {
        return n;
    } else {
        return f(b, n / b) + n % b;
    }
}

int main(void) {
    ll n, s;
    cin >> n;
    cin >> s;

    if (n == s) {
        cout << n + 1 << endl;
        return 0;
    }

    for (ll b = 2; b * b <= n; b++) {
        ll ans = f(b, n);
        if (f(b, n) == s) {
            cout << b << endl;
            return 0;
        }
    }

    ll ans = INF;
    for (ll c = 1; c * c <= n; c++) {
        if ((n - s) % c != 0) {
            continue;
        }
        ll b = (n - s) / c + 1;
        if (b < 2) {
            continue;
        }

        if (f(b, n) == s) {
            ans = min(ans, b);
        }
    }

    cout << (ans == INF ? -1 : ans) << endl;
    return 0;
}



Measured memory_bytes: 256
n = gets.to_i

taro = 0
hanako = 0
n.times.each do
   t,h = gets.split
   taro += 3 if t > h
   hanako += 3 if h > t
   taro += 1 if h == t
   hanako += 1 if h == t
end

puts [taro,hanako].join(" ")

Measured memory_bytes: 8756
#include <stdio.h>
#include <stdlib.h>

int compar(const int *val1, const int *val2) {
    if ( *val1 < *val2 ) {
	return -1;
    } else if ( *val1 == * val2 ) {
	return 0;
    } else {
        return 1;
    }
}

int main(){
  int n;
  scanf("%d\n",&n);
  int d[n];
  for (int i = 0; i < n; ++i) {
    scanf("%d", &d[i]);
  }
  qsort(d,n,sizeof(int),(int (*)(const void *, const void *))compar);
  int min = d[n/2-1], max = d[n/2];
  int answer = max-min;
  if(max == min) answer = 0;
  printf("%d",answer);
  return 0;
}

Measured memory_bytes: 892
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    n = ni()
    a = nl()
    print(sum(1 for i in range(0, n, 2) if a[i] & 1))
    return

solve()


Measured memory_bytes: 9188
#include <stdio.h>

int main(void)
{
	int n;
	int i;
	int count;
	
	while (1){
		count = 0;
		scanf("%d", &n);
		
		if (n == 0){
			break;
		}
		for (i = 0; i < 200; i++){
			if (n % 2 == 0){
				n /= 2;
				count++;
			}
			else if (n != 1){
				n *= 3;
				n += 1;
				count++;
			}
		}
		printf("%d\n", count);
	}
	
	return (0);
}

Measured memory_bytes: 596
import math
import fractions
import copy
import numpy as np
def j(q):
    if q==1: print("YES")
    elif q == 0:print("NO")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def printrow(a):
    for i in a:
        print(i)
"""
#decomment when needed
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
"""
n = ip()
a  = iprow()
ans = sum(a)
b = iprow()
pl = 0
pr = n-1
if n==1:
    print(min(sum(b),sum(a)))
    exit(0)

while pl <= pr:
    if b[pl] - a[pl]>0:
        b[pl] -= a[pl]
        a[pl] = 0
    else:
        a[pl]-=b[pl]
        b[pl] = 0
    if b[pl]:
        if b[pl] - a[pl+1]>0:
            b[pl] = 0
            a[pl+1] = 0
        else:
            a[pl+1]-=b[pl]
            b[pl] = 0
    if b[pr] - a[pr+1] > 0:
        b[pr] -= a[pr + 1]
        a[pr+1] = 0
    else:
        a[pr+1] -= b[pr]
        b[pr] = 0
    if b[pr]:
        if b[pr] - a[pr] > 0:
            a[pr] = 0
            b[pr] = 0
        else:
            a[pr] -= b[pr]
            b[pr] = 0
    pl+=1
    pr-=1
print(ans-sum(a))

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

#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fi first
#define se second
#define SZ(x) ((int)(x).size())

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;

/* --------------- fast io --------------- */ // begin
namespace Fread{
const int MAXN=1<<20;
char buf[MAXN],*S,*T;
inline char getchar(){
	if(S==T){
		T=(S=buf)+fread(buf,1,MAXN,stdin);
		if(S==T)return EOF;
	}
	return *S++;
}
}//namespace Fread
namespace Fwrite{
const int MAXN=1<<20;
char buf[MAXN],*S=buf,*T=buf+MAXN;
inline void flush(){
	fwrite(buf,1,S-buf,stdout);
	S=buf;
}
inline void putchar(char c){
	*S++=c;
	if (S==T)flush();
}
struct _{
	~_(){flush();}
}__;
}//namespace Fwrite

#ifdef ONLINE_JUDGE
	#define getchar Fread::getchar
	#define putchar Fwrite::putchar
#endif

template<typename T>inline void read(T& x){
	x=0;int f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c))x=x*10+(c-'0'),c=getchar();
	x*=f;
}
template<typename T>inline void write(T x,bool _enter=0,bool _space=0){
	if (!x)putchar('0');else{
		if(x<0)putchar('-'),x=-x;
		static char dig[41];
		int top=0;
		while(x)dig[++top]=(x%10)+'0',x/=10;
		while(top)putchar(dig[top--]);
	}
	if(_enter)putchar('\n');
	if(_space)putchar(' ');
}

namespace Fastio{
struct reader{
	template<typename T>reader& operator>>(T& x){::read(x);return *this;}
	reader& operator>>(char& c){
		c=getchar();
		while(c=='\n'||c==' ')c=getchar();
		return *this;
	}
	reader& operator>>(char* str){
		int len=0;
		char c=getchar();
		while(c=='\n'||c==' ')c=getchar();
		while(c!='\n'&&c!=' ')str[len++]=c,c=getchar();
		str[len]='\0';
		return *this;
	}
}cin;
const char endl='\n';
struct writer{
	template<typename T>writer& operator<<(T x){::write(x,0,0);return *this;}
	writer& operator<<(char c){putchar(c);return *this;}
	writer& operator<<(const char* str){
		int cur=0;
		while(str[cur])putchar(str[cur++]);
		return *this;
	}
}cout;
}//namespace Fastio
#define cin Fastio::cin
#define cout Fastio::cout
#define endl Fastio::endl
/* --------------- fast io --------------- */ // end

const int MAXN=1e5;
const ll INF=1e18;
inline void cmax(ll& x,ll y){x=(x>y?x:y);}

int n,a[MAXN+5],op[MAXN+5];
ll dp[MAXN+5][3];

int main() {
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		if(i!=n){
			char c;cin>>c;
			op[i]=(c=='+'?1:-1);
		}
	}
	op[0]=1;
	dp[0][1]=dp[0][2]=-INF;
	for(int i=1;i<=n;++i){
		dp[i][0]=dp[i][1]=dp[i][2]=-INF;
		for(int j=0;j<=2;++j)if(dp[i-1][j]!=-INF){
			cmax(dp[i][j],dp[i-1][j]+((j&1)?-1:1)*op[i-1]*a[i]);
			if(op[i-1]==-1&&j!=2){
				cmax(dp[i][j+1],dp[i-1][j]+(j==0?-1:1)*a[i]);
			}
			if(j!=0){
				cmax(dp[i][j-1],dp[i-1][j]+((j&1)?-1:1)*op[i-1]*a[i]);
			}
		}
	}
	cout<<dp[n][0]<<endl;
	return 0;
}

Measured memory_bytes: 4352
while True:
        n = int(input())
        if n == 0:
            break
        a = input().split()
        candidate = [["A",0],["B",0],["C",0],["D",0],["E",0],["F",0],["G",0],["H",0],["I",0],["J",0],["K",0],["L",0],["M",0],["N",0],["O",0],["P",0],["Q",0],["R",0],["S",0],["T",0],["U",0],["V",0],["W",0],["X",0],["Y",0],["Z",0]]
        for i in range(n):
            for c in candidate:
                if a[i] == c[0]:
                    c[1] += 1
                    break
            candidate.sort(key = lambda x:x[1],reverse =True)
            if candidate[0][1] > candidate[1][1] + n-(i+1):
                print(candidate[0][0],i+1)
                break
        else:
            print('TIE')




Measured memory_bytes: 5624
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
#======================================================#
def main():
    n, k = MII()
    aa = MII()
    print((-(-(n-1)//(k-1))) if n > 3 else 1)


if __name__ == '__main__':
    main()

Measured memory_bytes: 14008
N, M = map(int, input().split())
s = [0] * M
for i in range(M):
    s[i] = list(map(int, input().split()))[1:]
    s[i] = [v - 1 for v in s[i]]

p = list(map(int, input().split()))

ans = 0
for i in range(1 << N):
    all_lit = True
    for j in range(M):
        n = 0
        for k in s[j]:
            n += bool(i & (1 << k))
        if n % 2 != p[j]:
            all_lit = False
            break
    ans += all_lit

print(ans)


Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int main()
{
    std::string S;
    int N, K;
    std::cin >> N >> K;
    std::cin >> S;

    std::vector<int> Nums;
    int now = 1;
    int cnt = 0;
    for (int i = 0; i < N; ++i)
    {
        if (S[i] == (char)('0' + now))
        {
            cnt++;
        }
        else
        {
            now = 1 - now;
            Nums.emplace_back(cnt);
            cnt = 1;
        }
    }
    if (cnt != 0)
    {
        Nums.emplace_back(cnt);
    }

    if (Nums.size() % 2 == 0)
    {
        Nums.emplace_back(0);
    }

    int add = 2 * K + 1;
    int ans = 0;

    int left = 0;
    int right = 0;
    int tmp = 0; //[left,right) sum

    for (int i = 0; i < Nums.size(); i += 2)
    {
        int nextLeft = i;
        int nextRight = std::min(i + add, (int)Nums.size());

        while (nextLeft > left)
        {
            tmp -= Nums[left];
            left++;
        }
        while (nextRight > right)
        {
            tmp += Nums[right];
            right++;
        }
        ans = std::max(tmp, ans);
    }

    std::cout << ans << std::endl;

    return 0;
}

Measured memory_bytes: 1020
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, pair<ll, ll> > P3;
const ll MOD = 1000000007;
const int IINF = INT_MAX;
const ll LLINF = LLONG_MAX;
const int MAX_N = int(1e5 + 5);
const double EPS = 1e-10;
const int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define ALL(v) (v).begin(), (v).end()


int n, a[5005], dp[5005][5005]; // いまi番目その前にj番目を使ったときの最長

int main() {
    cin >> n;
    REP(i,n) cin >> a[i];
    sort(a,a+n);
    REP(i,n)fill(dp[i],dp[i]+n,2);
    REP(i,n){
        REP(j,i){
            int dif = a[i]-a[j], k;
            k = lower_bound(a,a+n,a[i]+dif) -a;
            if(k < n && a[k] == a[i]+dif){
                dp[k][i] = max(dp[k][i], dp[i][j] + 1);
            }
        }
    }
    int ans = 0;
    REP(i,n)REP(j,i) ans = max(ans, dp[i][j]);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 100896
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll ans=-1e18,sum,num;
    bool maki[3];
    ll n,m;
    cin>>n>>m;
    ll x[n],y[n],z[n];
    for(int i=0;i<n;i++){
        cin>>x[i]>>y[i]>>z[i];
    }
    vector<ll> v;
    for(ll bit=0LL;bit<8LL;bit++){
        sum=0LL;
        v.clear();
        for(int i=0;i<3;i++){
            if(bit&(1<<i))maki[i]=true;
            else maki[i]=false;
        }
        for(int i=0;i<n;i++){
            num=((maki[0])?x[i]:-x[i])+((maki[1])?y[i]:-y[i])+((maki[2])?z[i]:-z[i]);
            v.pb(num);
        }
        sort(be(v));
        reverse(be(v));
        for(int i=0;i<m;i++){
            sum+=v[i];
        }
        ans=max(ans,sum);
    }
    cout << ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
using namespace std;
typedef long long ll;
inline int read(){
	int n=0;char c;
	for(c=getchar();c<'0'||c>'9';c=getchar());
	for(;c>='0'&&c<='9';c=getchar()) n=n*10+c-48;
	return n;
}
const int maxn=2e5+5;
int n,i,j,l,r;ll x[maxn],ans,X,s[maxn],sum,now,k;
int main(){
	n=read(),X=read();
	fo(i,1,n) x[i]=read(),s[i]=s[i-1]+x[i];
	ans=s[n]*5+(X*n<<1);
	fd(i,n-1,1){
		now=X*(i+n);
		for(r=n,k=1;r;r=l,k++){
			l=r-i,l=l>0?l:0;
			sum=s[r]-s[l];
			if (r==n) now+=sum*5;else
			now+=(k<<1|1)*sum;
			if (now>=ans) break;
		}
		ans=now<ans?now:ans;
	}printf("%lld\n",ans);
} 

Measured memory_bytes: 3328
#include <cstdio>
#include <string>
#include <vector>
#include <map>
using namespace std;
static map<char, int> create_map() {
    map<char, int> m;
    string base = "abcdefghijklmnopqrstuvwxyz";
    for (int i = 0; i < 26; i++) m.insert({base[i], i});
    return m;
}
static map<char, int> m = create_map();
static string base = "abcdefghijklmnopqrstuvwxyz";
string str;
static int t1[4] = {0, 14, 7, 0}; //that
static int t2[4] = {0, 14, 15, 25}; //this
static int t3[3] = {0, 14, 11}; //the
int cdiff;

int main(void){

    char chs[81];
    while(fgets(chs, 81, stdin) != 0){
        str = chs;
        cdiff = 27;
        int sidx;
        for (int i = 0; i < str.size()-2; i++) {
            if (cdiff != 27) break;
            sidx = m[str[i]];
            //if character is a space or a point or distance between current and next character is not that we expected...
            if (str[i+1] == '.' || str[i+1] == ' ' || base[(sidx+t3[1])%26] != str[i+1]) continue;
            if (str[i+2] != '.' && str[i+2] != ' ' && base[(sidx+t3[2])%26] == str[i+2]) { cdiff = sidx - m['t']; break; }
            if (i < str.size()-3) {
                if (str[i+2] == '.' || str[i+3] == '.' || str[i+2] == ' ' || str[i+3] == ' ') continue;
                if (base[(sidx+t1[2])%26] == str[i+2] && base[(sidx+t1[3])%26] == str[i+3]) { cdiff = sidx-m['t']; break; }
                if (base[(sidx+t2[2])%26] == str[i+2] && base[(sidx+t2[3])%26] == str[i+3]) { cdiff = sidx-m['t']; break; }
            }
        }
        map<char, char> m2;
        for (int i = 19; i < 45; i++) m2.insert({base[(cdiff+i)%26], base[i%26]});
        m2.insert({'.', '.'}); m2.insert({' ', ' '});
        string str2 = "";
        for (int i = 0; i < str.size(); i++) {
            str2 += m2[str[i]];
        }
        printf("%s\n", str2.c_str());
    }


    return 0;
}



Measured memory_bytes: 2652
#[allow(unused_imports)]
use std::cmp::*;
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n = read();
    let t: isize = read();

    let mut ans = 10000;
    for _ in 0..n {
        let c = read();
        let t_i: isize = read();
        if t_i <= t {
            ans = min(ans, c);
        }
    }
    if ans == 10000 {
        println!("TLE");
    } else {
        println!("{}", ans);
    }
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pi pair<int, int>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define PI acos(-1.0)
using namespace std;
ll n, a[3030], Dp[3030][3030];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i=1; i<=n; i++) cin >> a[i];
    
    for (int i=n; i>0; i--)
        for (int j = i; j<=n; j++)
            Dp[i][j] = max(a[i] - Dp[i+1][j], a[j] - Dp[i][j-1]);

    cout << Dp[1][n] << '\n';
    return 0;
}


Measured memory_bytes: 71936
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a,b,c,d;
cin >> a >> b >> c >> d;
if(a+b<c+d)
cout << "Right";
else if(a+b==c+d)
cout << "Balanced";
else cout << "Left";
return 0;
}

Measured memory_bytes: 256