akhauriyash/Code-Regression huggingface dataset:
//              +-- -- --++-- +-In the name of ALLAH-+ --++-- -- --+              \\

#include <bits/stdc++.h>

#define F first
#define S second
#define _sz(x) (int)x.size()

using namespace std ;
using ll = long long ;
using ld = long double ;
using pii = pair <int , int> ;

int const MAX = 1000 + 20 ;
int n , k ;
vector <int> vec[MAX] ;

inline void next (int &a , int &b) {
	b ++ ;
	if (b == k) {
		a ++ ;
		b = a + 1 ;
	}
}

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

	cin >> n ;

	while ((k + 1) * k / 2 <= n) k ++ ;

	if (k * (k - 1) / 2 != n) return cout << "No\n" , 0 ;

	int a = 0 , b = 1 ;

	for (int i = 0 ; i < n ; i ++) {
		vec[a].push_back(i) ;
		vec[b].push_back(i) ;

		next(a , b) ;
	}

	cout << "Yes\n" ;

	cout << k << '\n' ;
	for (int i = 0 ; i < k ; i ++) {
		cout << k - 1 << ' ' ;
		for (int x : vec[i]) cout << x + 1 << ' ' ;
		cout << '\n' ;
	}
}

Measured memory_bytes: 2304
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int h = sc.nextInt();
		int area = (a+b)*h/2;
		System.out.println(area);
	}
}

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

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

  int c[3][3];
  for(int i  =0; i < 3; i++){
    for(int j = 0; j < 3; j++){
      cin >> c[i][j];
    }
  }

  int a[3],b[3];
  for(int i = 0; i <= 100; i++){

    a[0] = i;
    bool judge = true;
    for(int j = 0; j < 3; j++){
      b[j] = c[0][j]-a[0];
      if(b[j] < 0) judge = false;
    }

    a[1] = c[1][0]-b[0];
    for(int j = 0; j < 3; j++){
      if(b[j] < 0 || b[j] != c[1][j]-a[1]) judge = false;
    }

    a[2] = c[2][0] - b[0];
    for(int j = 0; j < 3; j++){
      if(b[j] < 0 || b[j] != c[2][j]-a[2]) judge = false;
    }
    if(a[1] < 0 || a[2] < 0) judge = false;

    if(judge){
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 256
a = list(map(int,input().split()))
haiku_5 = 2
haiku_7 = 1

num_5 = a.count(5)
num_7 = a.count(7)

if(num_5 == haiku_5 and num_7 == haiku_7):
    print('YES')
else:
    print('NO')

Measured memory_bytes: 2940
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <iomanip>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

using namespace std;
 
#define ull unsigned long long
#define ll long long
#define mod 1000000007
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define PI acos(-1.0)
const int N=1e5 + 5;
const int M=1e5 + 5;
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    int aa,bb,xx;
    double a,b,x;
    cin>>aa>>bb>>xx;
    a = aa;
    b = bb;
    x = xx;
    double t = 0.5*a*a*b;
    if(x>=t){
        double area = a*a*b - x;
        area /= a;
        double l = 2*area/a;
        double ang = atan(a/l);
        ang *= 180.0/PI;
        ang = 90.0-ang;
        cout << fixed << setprecision(12) << ang << endl;
    }   
    else{
        double area = x/a;
        double l = 2*area/b;
        double ang = atan(l/b);
        ang *= 180.0/PI;
        ang = 90.0-ang;
        cout << fixed << setprecision(12) << ang << endl; 
    }  


 
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <string.h>
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>

using namespace std;

const int N = 110;
string a[N];
vector<vector<int> > f(N, vector<int>(N, (int)1e9));
int n, m;

void iniv() {
	f[0][0] = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (i) f[i][j] = min(f[i][j], f[i - 1][j] + (a[i - 1][j] != a[i][j]));
			if (j) f[i][j] = min(f[i][j], f[i][j - 1] + (a[i][j - 1] != a[i][j]));
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> a[i];
	
	iniv();

	int res = f[n - 1][m - 1];
	if (a[0][0] == '#') res++;
	if (a[n - 1][m - 1] == '#') res++;
	cout << res / 2 << '\n';

	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<map>

#define fst first
#define snd second

using namespace std;
typedef pair<int,int> pt;
typedef long long int lli;

int usa_x[600], usa_y[600], usa_xy[2];
int cat_x[600], cat_y[600], cat_xy[2];
int usa_cnt, cat_cnt;
map<lli,pt> usa_board, cat_board;

int main(void) {
    int n,u,v,m;
    scanf("%d%d%d%d",&n,&u,&v,&m);
    if(n==1) u*=4, v*=4;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++) {
            lli x;
            scanf("%lld",&x);
            usa_board[x] = pt(j,i);
        }
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++) {
            lli a;
            scanf("%lld",&a);
            cat_board[a] = pt(j,i);
        }

    for(int i=0; i<m; i++) {
        lli a;
        scanf("%lld",&a);

        if(usa_board.find(a) != usa_board.end()) {
            int x = usa_board[a].fst;
            int y = usa_board[a].snd;

            usa_x[x]++; usa_y[y]++;
            if(usa_x[x] == n) usa_cnt++;
            if(usa_y[y] == n) usa_cnt++;
            if(x==y) {
                usa_xy[0]++;
                if(usa_xy[0] == n) usa_cnt++;
            }
            if(x+y==n-1) {
                usa_xy[1]++;
                if(usa_xy[1] == n) usa_cnt++;
            }
        }

        if(cat_board.find(a) != cat_board.end()) {
            int x = cat_board[a].fst;
            int y = cat_board[a].snd;

            cat_x[x]++; cat_y[y]++;
            if(cat_x[x] == n) cat_cnt++;
            if(cat_y[y] == n) cat_cnt++;
            if(x==y) {
                cat_xy[0]++;
                if(cat_xy[0] == n) cat_cnt++;
            }
            if(x+y==n-1) {
                cat_xy[1]++;
                if(cat_xy[1] == n) cat_cnt++;
            }
        }

        if(usa_cnt >= u || cat_cnt >= v)
            break;
    }

    if(usa_cnt >= u && cat_cnt < v)
        puts("USAGI");
    else if(usa_cnt < u && cat_cnt >= v)
        puts("NEKO");
    else
        puts("DRAW");

    return 0;
}

Measured memory_bytes: 20592
#include<cstdio>

int main(void){
	int a, b;
	char op;
	
	while(1){
		scanf("%d %c %d", &a, & op, &b);
		if (op == '+' ) printf("%d\n", a + b);
		else if (op == '-' ) printf("%d\n", a - b);
		else if (op == '*' ) printf("%d\n", a * b);
		else if (op == '/' ) printf("%d\n", a / b);
		else if (op == '?' ) break;
	}
		
	return 0;
}

Measured memory_bytes: 1032
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] num = new int[10000];
		for (int i = 0; i < 10000; i++) {
			String line = sc.nextLine();
			num[i] = Integer.parseInt(line);
			if (num[i] == 0) {
				break;
			}
		}
		for (int i = 0; i < num.length; i++) {
			if (num[i] == 0) {
				break;
			}
			System.out.println("Case " + (i + 1) + ": " + num[i]);
		}
	}
}

Measured memory_bytes: 60396
#include<bits/stdc++.h>
using namespace std;
int a,b,c;
int read()
{
	int s=0;
	char c=getchar();
	while(!isdigit(c))
		c=getchar();
	while(isdigit(c))
	{
		s=(s<<1)+(s<<3)+c-'0';
		c=getchar();
	}
	return s;
}
int main()
{
	a=read();b=read();c=read();
	if(b-a==c-b)
		printf("YES");
	else
		printf("NO");
	return 0;
}

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

void affine(int a,int b,char t[]){
	int i;
	for(i=0;i<4;i++){
		t[i]='a'+(a*(t[i]-'a')+b)%26;
	}
}

int main(void){
	char text[260],t[8],d[26];
	int n,a,b,x,i;

	scanf("%d",&n);
	fgets(text,260,stdin);
	for(1;n>0;n--){
		fgets(text,260,stdin);x=0;
		for(a=1;a<26 && x==0;a+=2){
			if(a==13)continue;
			for(b=0;b<26 && x==0;b++){
				strcpy(t,"this");affine(a,b,t);
				if(strstr(text,t)!=NULL){x=1;break;}
				strcpy(t,"that");affine(a,b,t);
				if(strstr(text,t)!=NULL){x=1;break;}
			}
		}

		if(x>0){
			a-=2;
			for(i=0;i<26;i++)d[i]='a'+(a*i+b)%26;
			x=strlen(text);

			for(x--;x>=0;x--){
				if('a'<=text[x] && text[x]<='z'){
					for(i=0;i<26;i++){
						if(d[i]==text[x]){text[x]='a'+i;break;}
					}
				}
			}
		}else return 1;

		printf("%s",text);
	}

	return 0;
}

Measured memory_bytes: 612
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <sstream>
#include <cassert>
#include <ctime>
#include <list>
using namespace std;
static const double EPS = 1e-6;
typedef long long ll;
typedef pair<int,int> PI;
#ifndef M_PI
const double M_PI=acos(-1);
#endif
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define SZ(a) (int((a).size()))
#define F first
#define S second
int dx[]={0,1,0,-1,0,0},dy[]={1,0,-1,0,0,0};
int dz[]={0,0,0,0,1,-1};

int n;
double sx[30],sy[30],sz[30];

double dist(double x,double y,double z,int id){
  double tx=x-sx[id];
  double ty=y-sy[id];
  double tz=z-sz[id];
  return sqrt(tx*tx+ty*ty+tz*tz);
}

double rad(double x,double y,double z){
  double ret=dist(x,y,z,n-1);
  rep(i,n-1)ret=max(ret,dist(x,y,z,i));
  return ret;
}

typedef struct _node{
  double x,y,z,r;
  int wh;
  _node(double x,double y,double z,int wh):
    x(x),y(y),z(z),wh(wh),r(rad(x,y,z)){};

  bool operator<(const _node& rn)const{
    if(rn.wh!=wh)return rn.wh<wh;
    return rn.r<r;
  }
}node;

int tx[]={1,1,1,1,-1,-1,-1,-1};
int ty[]={1,1,-1,-1,1,1,-1,-1};
int tz[]={1,-1,1,-1,1,-1,1,-1};
double len[1000];

void solve(){
  rep(i,n)scanf("%lf%lf%lf",sx+i,sy+i,sz+i);
  len[0]=100;
  for(int i=1;i<1000;++i)
    len[i]=len[i-1]/2;
  double ans=10000;
  rep(i,n)rep(j,i)
    ans=min(ans,rad((sx[i]+sx[j])/2,
                    (sy[i]+sy[j])/2,
                    (sz[i]+sz[j])/2));

  priority_queue<node> q;
  q.push(node(50,50,50,0));
  int cu=0;
  int bwh=-1;
  while(!q.empty()){
    node cur=q.top();
    q.pop();
    if(cu==200 && cur.wh==bwh)continue;
    if(cu==200)cu=0,bwh=cur.wh;
    ++cu;
    double rr=len[cur.wh];    
    if(ans<cur.r-rr*sqrt(3)*2+EPS)continue;
    ans=min(ans,cur.r);
    if(cur.wh>25)continue;
    //printf("%.5f %.5f %.5f %.5f %.7f %d\n",cur.x,cur.y,cur.z,cur.r,ans,cur.wh);

    rep(i,8)
      q.push(node(cur.x+rr*tx[i],cur.y+rr*ty[i],cur.z+rr*tz[i],cur.wh+1));
  }

  printf("%.5f\n",ans);
}

main(){
  while(cin>>n,n)
    solve();
}

Measured memory_bytes: 0
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.next();
        if (S.contains("R")) {
            if (S.charAt(1) == 'S') {
                System.out.println(1);
            } else {
                if (S.equals("RRR")) {
                    System.out.println(3);
                } else if (S.equals("SRS")) {
                    System.out.println(1);
                } else {
                    System.out.println(2);
                }
            }
        } else {
            System.out.println(0);
        }
    }
}

Measured memory_bytes: 35604
import scala.io.StdIn.readLine

object Main extends App {
  var n:Array[Int] = readLine.split(" ").map(_.toInt)

  while( n(0) != -1 || n(1) != -1 || n(2) != -1 ) {
    val Array(m,f,r) = n
    val score = m+f
    var grade = ""

    if( m == -1 || f == -1)
      grade = "F"
    else if(score >= 80)
      grade = "A"
    else if(score < 80 && score >= 65)
      grade = "B"
    else if(score < 65 && score >= 50)
      grade = "C"
    else if(score < 50 && score >= 30)
      if(r>=50)
          grade = "C"
      else
          grade = "D"
    else
        grade = "F"

    println(grade)


    n = readLine.split(" ").map(_.toInt)
  }
}

Measured memory_bytes: 44056
if __name__ == '__main__':
    N, Q= map(int, input().split())
    S = str(input())
    L = [list(map(int, input().split())) for _ in range(Q)]
    
    nums = [0]*(N-1)
    
    for i in range(N-1):
        if S[i] == 'A' and S[i+1] == 'C':
            nums[i] += 1

    for i in range(1, len(nums)):
        nums[i] = nums[i] + nums[i-1]
    
    nums = [0] + nums
    
    for l, r in L:
        print(nums[r-1] - nums[l-1])

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


def main():
    N, M = map(int, input().split())
    H = list(map(int, input().split()))

    result = [1] * N

    for i in range(M):
        a, b = map(int, input().split())
        if H[a - 1] <= H[b - 1]:
            result[a - 1] *= 0
        if H[a - 1] >= H[b - 1]:
            result[b - 1] *= 0
    print(result.count(1))


if __name__ == "__main__":
    main()


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

int main(void){
    int n;
    int i, k;
    int result = 0;

    cin >> n;
    int div = 0;

    for(i=1; i<n+1; i+=2){
        div = 0;
        for(k=1; k<n+1; k+=2){
            if(i%k == 0) div++;
        }
        if(div==8){
            result++;
        }
    }

    cout << result << endl;;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string>
#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <algorithm>
#include <map>
#include <iterator>
#include <limits>
#include <numeric>
#include <type_traits>
#include <cmath>
#include <cstdlib>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;

#define ALL(v) (v).begin(), (v).end()
#define endl "\n"
typedef long long int ll;

template<typename T>
ostream& operator << (ostream& os, vector<T>& vec) {
	for (int i = 0; i<vec.size(); i++) {
		os << vec[i] << (i + 1 == vec.size() ? "" : " ");
	}
	return os;
}

int SumDigitValues(int x)
{
	int sum = 0;
	while (x)
	{
		sum += x % 10;
		x = x / 10;
	}

	return sum;
}

int Factorial(int n)
{
	if (n < 0) return 0;
	if (n == 0) return 1;
	return n * Factorial(n - 1);
}

int factorial(int n)
{
	if (n > 1)
	{
		return n * factorial(n - 1);
	}
	else
	{
		return 1;
	}
}

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

vector<pair<ll, int>> factorize(ll n) 
{
	vector<pair<ll, int>> res;
	for (ll i = 2; i * i <= n; ++i)
	{
		if (n % i) continue;
		res.emplace_back(i, 0);
		while (n % i == 0)
		{
			n /= i;
			res.back().second++;
		}
	}
	if (n != 1) res.emplace_back(n, 1);
	return res;
}

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

	ll a, b;
	cin >> a >> b;
	ll maxCommonDivisor = gcd(a, b);
	auto commonDivisors = factorize(maxCommonDivisor);
	cout << (int)(commonDivisors.size() + 1) << endl;
}

Measured memory_bytes: 256
//
//  main.cpp
//
// https://atcoder.jp/contests/abc127/tasks/abc127_f

#include <algorithm>
#include <array>
#include <assert.h>
#include <functional>
#include <iostream>
#include <limits>
#include <math.h>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

using ll = long long;
using ull = unsigned long long;

int main(int argc, char* argv[]) {
    ll bs_sum = 0;
    priority_queue<ll> as_former;
    ll as_former_sum = 0;
    priority_queue<ll, vector<ll>, std::greater<ll>> as_latter;
    ll as_latter_sum = 0;
    int q;
    cin >> q;
    while (q > 0) {
        q--;
        int query_type;
        cin >> query_type;
        if (query_type == 1) {
            ll a,b;
            cin >> a >> b;
            bs_sum += b;
            if (as_former.empty() || a < as_former.top()) {
                as_former.push(a);
                as_former_sum += a;
            } else {
                as_latter.push(a);
                as_latter_sum += a;
            }
            while (as_latter.size() > as_former.size()) {
                ll v = as_latter.top();
                as_latter.pop();
                as_latter_sum -= v;
                as_former.push(v);
                as_former_sum += v;
            }
            while (as_former.size() > as_latter.size() + 1) {
                ll v = as_former.top();
                as_former.pop();
                as_former_sum -= v;
                as_latter.push(v);
                as_latter_sum += v;
            }
        } else {
            ll x = as_former.top();
            ll val = bs_sum + (x * (ll)as_former.size() - as_former_sum) + (as_latter_sum - x * (ll)as_latter.size());
            cout << x << " " << val << endl;
        }
    }
}

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

#define fi first
#define se second
#define fin(s) freopen( s, "r", stdin );
#define fout(s) freopen( s, "w", stdout );

const long long N = 303;
const long long mod = 1e9 + 7;
const long long block = 500;

using namespace std;

int n;
int m;
int d[N];
int a[N][N];
bool dead[N];

void solve()
{
        cin >> n >> m;
        for(int i = 1; i <= n; i++){
                for(int j = 1; j <= m; j++){
                        cin >> a[i][j];
                }
                d[a[i][1]]++;
        }
        int ans = n;
        for(int i = 1; i <= m; i++){
                int f = -1;
                for(int j = 1; j <= m; j++){
                        if(dead[j]){
                                continue;
                        }
                        if(f == -1 || d[j] > d[f]){
                                f = j;
                        }
                }
                ans = min(ans, d[f]);
                dead[f] = true;
                for(int j = 1; j <= m; j++){
                        d[j] = 0;
                }
                for(int j = 1; j <= n; j++){
                        for(int h = 1; h <= m; h++){
                                if(dead[a[j][h]]){
                                        continue;
                                }
                                d[a[j][h]]++;
                                break;
                        }
                }
        }
        cout << ans << "\n";
}

bool mtest = false; int main()
{
        //fin("input.txt");
        //fout("output.txt");
        //fin("landscape.in");
        //fout("landscape.out");
        ios_base::sync_with_stdio(0);
        int TE = 1;
        if(mtest)
                cin >> TE;
        while(TE--)
                solve();
        return 0;
}


Measured memory_bytes: 640
import java.util.Arrays;
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		new Main().run();
	}

	long MODULO = 1_000_000_000 + 7;

	void run() {
		Scanner sc = new Scanner(System.in);
		int s = sc.nextInt();
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] t = new int[n];
		int[] p = new int[n];
		int[] x = new int[s];
		for (int i = 0; i < s; ++i) {
			x[i] = sc.nextInt();
		}
		for (int i = 0; i < n; ++i) {
			t[i] = sc.nextInt();
			p[i] = sc.nextInt();
			--p[i];
		}
		int[] w = new int[n];
		for (int i = 0; i < n; ++i) {
			w[i] = t[i] - x[p[i]];
		}
		Arrays.sort(w);
		long ans = 0;
		for (long v : w) {
			ans -= v;
		}
		long[][] f = new long[n + 1][m + 1];
		for (int i = 0; i < f.length; ++i) {
			for (int j = 0; j < f[i].length; ++j) {
				f[i][j] = Integer.MAX_VALUE / 16;
			}
		}
		for (int i = 1; i < f.length; ++i) {
			f[i][1] = w[i - 1] * i;
		}

		for (int j = 2; j <= m; ++j) {
			// j is fixed.
			// Attention: h[i][k]:=f[k][j-1]+w[i-1]*(i-k) is of Monge.
			// min(h[i][]) can be enumerated in O(n*log(n))
			// f[i][j]=min(h[i][])
			long[] v = calc(f, w, j);
			for (int i = 1; i <= n; ++i) {
				// for (int k = 1; k <= i - 1; ++k) {
				// f[i][j] = Math.min(f[i][j], h(f, w, i, j, k));
				// }
				f[i][j] = v[i];
			}
		}

		long min = Integer.MAX_VALUE / 16;
		for (int j = 1; j <= m; ++j) {
			min = Math.min(min, f[n][j]);
		}
		ans += min;
		System.out.println(ans);
	}

	long[] calc(long[][] f, int[] w, int j) {
		int n = f.length - 1;
		int m = f[0].length - 1;
		long[] ret = new long[n + 1];
		Arrays.fill(ret, Integer.MAX_VALUE / 16);
		rec(ret, 1, n, 2, n + 1, f, w, j);
		return ret;
	}

	// [low,high)
	// [left,right)
	long rec(long[] ret, int low, int high, int left, int right, long[][] f, int[] w, int j) {
		int mid = (left + right) / 2;// the value of the variable i
		long v = Long.MAX_VALUE / 16;
		int arg = -1;
		for (int k = Math.max(0, low); k <= Math.min(mid - 1, high); ++k) {
			v = Math.min(v, h(f, w, mid, j, k));
			if (v == h(f, w, mid, j, k))
				arg = k;
		}
		if (right - left > 1) {
			rec(ret, low, arg, left, mid, f, w, j);
			rec(ret, arg, high, mid, right, f, w, j);
		}
		ret[mid] = v;
		return v;
	}

	long h(long[][] f, int[] w, int i, int j, int k) {
		return f[k][j - 1] + w[i - 1] * (i - k);
	}

	void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}

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

using namespace std;

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

    vector<long> a(n);
    for(auto &x: a) cin >> x;

    vector<long> b(n), c(n);
    copy(a.begin(), a.end(), b.begin());
    copy(a.begin(), a.end(), c.begin());

    for(int i=1; i<n; i++)
        b[i] += b[i-1];
    for(int i=1; i<n; i++)
        c[i] ^= c[i-1];

    long r = 0;
    {
        int ok = 0, ng = n;
        while(ng - ok > 1) {
            int m = (ok+ng)/2;
            if(b[m] == c[m])
                ok = m;
            else
                ng = m;
        }
        
        r += ok - 0 + 1;
    }

    for(int l=1; l<n; l++) {
        int ok = l, ng = n;
        while(ng - ok > 1) {
            int m = (ok+ng)/2;
            if(b[m] - b[l-1] == (c[m] ^ c[l-1]))
                ok = m;
            else
                ng = m;
        }
        
        r += ok - l + 1;
    }
    cout << r << endl;
}


Measured memory_bytes: 4992
#include<iostream>
#include<algorithm>
int main()
{
	int x, tag=0, count=0;
	scanf("%d", &x);
	for(int i=1;;i++)
	{
		tag+=x;
		count++;
		if(tag==360)
		{
				printf("%d", count);
				return 0;		
		}
		else
		{
			if(tag%360==0)
			{
				printf("%d", count);
				return 0;
			}
		}
	}
 }

Measured memory_bytes: 3812
#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstring>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <sstream>
#include <stdio.h>
#include <string>
#include <tuple>
#include <vector>
namespace mp = boost::multiprecision;
using namespace std;
using ull = unsigned long long;
using ld = long double;
//using ll = boost::multiprecision::cpp_int;
using ll = long long;
#define FORi(N) for(ll i = 0; i < N; ++i)
#define FORj(N) for(ll j = 0; j < N; ++j)
#define FORk(N) for(ll k = 0; k < N; ++k)
//using int = ll;
ll gcd(ll m, ll n) {
    if(n == 0)
        return abs(m);
    return (gcd(n, m % n));
}
void putYN(bool b) {
    if(b) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}
void swap(ll &a, ll &b) {
    ll tmp = a;
    a = b;
    b = tmp;
}
ll combi(ll n, ll k) {
    ll r = 1 ,rr =1;
    for(ll i=0;i<k;++i) {
      r*=(n-i);
      rr*=(i+1);
      //r %= 1000000007;
      //rr %= 1000000007;
    }
    r/=rr;
    //r %= 1000000007;
    return r;
}
ll kyori(vector<ll>& y,vector<ll>& z,ll D){
  ll a=0;
  FORi(D){
    a+=pow((long long)(y[i]-z[i]),2);
  }
  ll b =  ((ll)pow((ll)sqrt(a),2)==a);
  if(b) return 1;
  return 0;
}
int main() {
  ll N,D;
  cin>>N>>D;
  vector<vector<ll>> X(N);
  FORi(N){
    X[i] = vector<ll>(D);
    FORj(D){
      cin>>X[i][j];
    }
  }
  ll num = 0;
  FORi(N){
    FORj(N){
      if(i<=j)continue;
      num += (int)kyori(X[i],X[j],D);
    }
  }
  cout<<num<<endl;
  return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long int ll;
typedef string str;

int main ()
{
	// ios::sync_with_stdio(0);
 //    cin.tie(0);
 //    cout.tie(0);
	ll t,n,m,k,i,a,b,j;
	cin >> n;
	m=sqrt(n);
	vector <ll > v;
	vector < ll > p;
   	while (n % 2 == 0)  
    {  
        v.pb(2);  
        n = n/2;  
    }  
  
    for (i = 3; i <= sqrt(n); i = i + 2)  
    {  
        while (n % i == 0)  
        { 
        	v.pb(i); 
            n = n/i;  
        }  
    }  
  
    if (n > 2)
    	v.pb(n);

    for(i=0;i<v.size();i++)
    {
    	a=v[i];
    	t=0;
    	while(i<v.size() && v[i]==a)
    	{
    		t++;
    		i++;
    	}
    	p.pb(t);
    	i--;
    }
    a=0;
    for(i=0;i<p.size();i++)
    {
    	j=1;
    	b=1;
    	while(b<=p[i])
    	{
    		j++;
    		b+=j;
    	}
    	a+=j-1;
    }
    cout << a << "\n";
	return 0;
}

Measured memory_bytes: 3724
#include <bits/stdc++.h>
#define ff first
#define ss second
#define MAX 10005
#define endl "\n"
#define mp make_pair
#define pb push_back
#define int long long
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define vi vector<int>
#define mii map<int,int>
#define pii pair<int,int>
#define len(x) (x.size())
#define read(x) scanf("%lld",&x)
#define all(a) a.begin(),a.end()
#define write(x) printf("%lld",x)
#define rep(i,a) for(int i=0;i<a;i++)
#define f(i,a,b) for(int i=a;i<=b;i++)
#define debug(x) cerr<<#x<<": "<<x<<endl
#define pset(x,y) fixed<<setprecision(y)<<x
#define T int tc;cin>>tc;for(int t=1;t<=tc;t++)
#define set_arr(arr,i) memset(arr,i,sizeof(arr))
#define trace1(x)							cerr << #x << ": " << x << endl;
#define trace2(x, y)						cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)						cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       			cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    			cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) 			cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
using namespace std;

int n;
vi a(MAX),b(MAX);
int dp[MAX];

int solve(int h){
	if(h<=0) return 0;
	if(dp[h]!=-1) return dp[h];
	int ans = INT_MAX;
	for(int i=0;i<n;i++){
		ans = min(ans,b[i] + solve(h-a[i]));
	}
	return dp[h] = ans;
}

signed main(){
	
	int h;
	set_arr(dp,-1);
	cin>>h>>n;
	rep(i,n){
		cin>>a[i]>>b[i];
	}
	cout<<solve(h);
	return 0;
}


Measured memory_bytes: 896
import java.util.*;
class Main
{
    public static void main (String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] c = new int[n], s = new int[n], f = new int[n], ans = new int[n];
        for(int i = 0; i < n-1; i++){
            c[i] = sc.nextInt();
            s[i] = sc.nextInt();
            f[i] = sc.nextInt();
        }
        c[n-1] = s[n-1] = f[n-1] = 0; 
        for(int i = 0; i < n; i++){
            ans[i] = s[i] + c[i];
            for(int j = i+1; j < n-1; j++){
                ans[i] = Math.max(s[j], ((ans[i] + f[j] - 1) / f[j]) * f[j]);
                ans[i] += c[j]; 
            }
            System.out.println(ans[i]);
        }
    }
}

Measured memory_bytes: 27624
#include<iostream>
using namespace std;
int main(){
    int x,y;
    cin>>x>>y;
    if (x==y){cout<<"Draw";}
     else if(x>y&&y!=1){cout<<"Alice";}
   else if(x>y&&y==1){cout<<"Bob";}
   else if(x<y&&x!=1){cout<<"Bob";}
   else if(x<y&&x==1){cout<<"Alice";}



    return 0;

}





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

int main(){
  int N;
  cin >> N;
  int S = 0, M = 0;
  for(int i = 0; i < N; i++){
    int p;
    cin >> p;
    S += p;
    M = max(M, p);
  }
  int ans = S - M / 2;
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <cstdint>
#define INF 1000000000
#define LLINF 2000000000000000
#define MOD 1000000007
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define LOOP(i,N) for(int i=0;i<N;i++)
#define LOOP1(i,N) for(int i=1;i<=N;i++)
typedef pair<int,int> P;
typedef pair<int,pair<int,int> > PP;
#define int long long
int n,x,y;

// signed abs(int i){
//   if(i<0) return -i;
//   return i;
// }

// signed dist(int i,int j){
//   // return min(abs(i-x)+abs(j-y)+1, abs(j-i));
// }

signed main(){
  int n;
  cin >> n;
  int ans = 0;
  LOOP1(i,n){
    if(i%3 && i%5){
      ans+=i;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define ROF(i, a, b) for (int i = a; i >= b; i--)
using namespace std;

using pii = pair<int, int>; using vpii = vector<pii>;
using vi = vector<int>; using vvi = vector<vi>;
using ll = long long;
using pll = pair<ll, ll>; using vpll = vector<pll>;
using vll = vector<ll>; using vvll = vector<vll>;

const ll MOD = 1e9 + 7;
ll f[2000005];

ll bm(ll b, ll p) {
    ll rt = 1;
    for (ll i = 1, j = b; i <= p; i <<= 1, j = j * j % MOD) {
        if (i & p) rt = rt * j % MOD;
    }
    return rt;
}

ll ncr(ll n, ll r) {
    return f[n] * bm(f[n - r] * f[r] % MOD, MOD - 2) % MOD;
}

int main() {
    int k; cin >> k;
    string s; cin >> s;
    int sz = s.size();
    f[0] = 1;
    FOR(i, 1, k + sz)
        f[i] = f[i - 1] * i % MOD;
    ll ans = 0;
    FOR(i, sz, sz + k) {
        ans = (ans + ncr(i - 1, sz - 1) * (bm(25, i - sz) * bm(26, k + sz - i) % MOD)) % MOD;
    }
    cout << ans << endl;
}

Measured memory_bytes: 20020
<?php
	$keys = array();
	for( $i=0; $i<=ord('z')-ord('a'); $i++ ) {
		array_push( $keys, chr( ord('a')+$i ) );
	}
	$cnt = array_fill_keys( $keys, 0 );
	
	while( FALSE != ( $data = fgets( STDIN ) ) ) {
		$data = strtolower( trim( $data ) );
		
		$strs = str_split( $data );
		foreach( $strs as $c ) {
			if( 'a' <= $c && $c <= 'z' ) {
				$cnt[ $c ]++;
			}
		}
	}
	for( $i=0; $i<count( $cnt ); $i++ ) {
		print $keys[$i]." : ".$cnt[ $keys[$i] ].PHP_EOL;
	}
	return;
?>

Measured memory_bytes: 6840
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

ab = 0
leftb = 0
righta = 0
lbra = 0
n = inn()
for i in range(n):
    s = input()
    if s[0] == 'B' and s[-1] == 'A':
        lbra += 1
    if s[0] == 'B':
        leftb += 1
    if s[-1] == 'A':
        righta += 1
    for j in range(len(s)-1):
        if s[j:j+2] == 'AB':
            ab += 1

if DBG:
    print("ab {} l {} r {} lbra {} ".format(ab, leftb, righta, lbra))
print(ab + (max([0,lbra-1]) if lbra==leftb and leftb==righta else min([leftb, righta])))


Measured memory_bytes: 3316
//Robs Code
/***********HEADER***************/
#include <iostream>
#include <bitset>
#include <deque>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#include <list>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <set>
#include <queue>
#include <map>
/***********MACROS***************/
#define int long long int
#define fri(l,k) for (i=l;i<=k;i++)
#define frj(l,k) for (j=l;j>=k;j--)
#define fij(a,b,l,k) for(i=a;i<=b;i++) for(j=l;j<=k;j++)
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define endl "\n"
#define pb push_back
#define _1 first
#define _2 second
#define mxsz 1000000007
#define mxval 1e9 + 7
#define grt [](auto x,auto y){return x>y;}
#define pii pair<int,int>
/*********VARIABLE****************/
using namespace std;
int i,j,n,m,k,l,q,t,a,b,sum[3],tot[3],cnt[3];
/*********FUNCTIONS**************/
int powom(int a,int b) {
    int result = 1;
    while (b > 0) {
        if (b & 1)
            result = result * a;
        a = a * a;
        b >>= 1;
    }
    return result;
}
/***********MAIN**************/
signed main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	cin>>n;
	int x;
	cin>>x;
	int sum = x;
	for(int i=1;i<(n-1);i++){
		int y;
		cin>>y;
		sum+=min(x,y);
		x = y;
	}
	sum+=x;
	cout<<sum<<"\n";
	return 0;
}
//.........

Measured memory_bytes: 256
#B- Frog 2

def solution(nums):
    n = len(nums)
    dp = [0,0,0]
    for day in range(n):
        new_dp = [0,0,0]
        for i in range(3):
            for j in range(3):
                if i!=j:
                    new_dp[i] = max(new_dp[i] , dp[j]+ nums[day][i] )
        dp = new_dp
    return max(dp[0],dp[1],dp[2])

N = int(input())
nums = []
for _ in range(N):    
    day = list(map(int,input().split()))
    nums.append(day)
res = solution(nums)
print(res)


Measured memory_bytes: 30196
import java.io.IOException;
import java.io.InputStream;
import java.util.*;

public class Main {
	
    public static void main(String[] args) {
    	FastScanner sc = new FastScanner();
 
    	int n = sc.nextInt();
    	int k = sc.nextInt();
    	
    	char[] c = sc.next().toCharArray();
    	switch(c[k-1]){
    	case 'A':
    		c[k-1] = 'a';
    		break;
    	case 'B':
    		c[k-1] = 'b';
    		break;
    	default:
    		c[k-1] = 'c';
    		break;
    	}
    	
    	for(int i=0;i<n;i++){
    		System.out.print(c[i]);
    	}
    }
}


class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() { return Double.parseDouble(next());}
}

Measured memory_bytes: 22484
#include <algorithm>
#include <bitset>
#include <cmath>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>

// Acknowledgement: Special thanks to kyomukyomupurin, who developed this
// template.
template <class T, class U>
std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) {
  return os << '(' << p.first << ", " << p.second << ')';
}

template <class T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) {
  int n = 0;
  for (auto e : vec) os << (n++ ? ", " : "{") << e;
  return os << (n ? "}" : "{}");
}

template <class T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& st) {
  int n = 0;
  for (auto e : st) os << (n++ ? ", " : "{") << e;
  return os << (n ? "}" : "{}");
}

template <class T, class U>
std::ostream& operator<<(std::ostream& os, const std::map<T, U>& mp) {
  int n = 0;
  for (auto e : mp) os << (n++ ? ", " : "{") << e;
  return os << (n ? "}" : "{}");
}

template <class T>
std::istream& operator>>(std::istream& is, std::vector<T>& vec) {
  for (T& e : vec) is >> e;
  return is;
}

#ifdef LOCAL
#define debug(...) \
  std::cerr << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

void debug_out() { std::cerr << '\n'; }

template <class Head, class... Tail>
void debug_out(Head&& head, Tail&&... tail) {
  std::cerr << head;
  if (sizeof...(Tail) != 0) std::cerr << ", ";
  debug_out(std::forward<Tail>(tail)...);
}
using namespace std;
using int64 = long long;

int64 compare_two_int64(int64 a, int64 b) {
  if (a > b)
    return 1;
  else if (a == b)
    return 0;
  else
    return -1;
}

int main() {
  int64 N;
  cin >> N;
  vector<int64> A(N);
  cin >> A;
  int64 count = 0;
  int64 trend;
  int64 trend_prev = compare_two_int64(A[0], A[1]);
  bool is_first_element = 0;
  for (int64 i = 1; i < N - 1; i++) {
    if (is_first_element) {
      is_first_element = 0;
      trend_prev = compare_two_int64(A[i], A[i + 1]);
      continue;
    }
    trend = compare_two_int64(A[i], A[i + 1]);
    if (trend * trend_prev == -1) {
      count++;
      is_first_element = 1;
    }
    if (trend != 0) trend_prev = trend;
  }
  cout << count + 1 << endl;
  return 0;
}

Measured memory_bytes: 1152
<?php

$s = trim(fgets(STDIN));
$p = trim(fgets(STDIN));

$array = [];
for($i=0; $i<strlen($s); $i++){
    if(strlen(substr($s, $i, strlen($p))) < strlen($p)){
        $array[] = substr($s, $i, strlen($p)) . substr($s, 0, strlen($p)-(strlen($s)-$i));
    }else{
        $array[] = substr($s, $i, strlen($p));
    }
}
if(in_array($p, $array)){
    echo 'Yes',PHP_EOL;
}else{
    echo 'No',PHP_EOL;
}


Measured memory_bytes: 9304
a, b, c, d, e = [int(input()) for i in range(5)]
k = int(input())
if max(e-a, e-b, d-a, e-c, d-b, c-a, e-d, d-c, c-b, b-a) > k:
  print(":(")
else:
  print("Yay!")

Measured memory_bytes: 3060
def div(c,n):
    d={}
    while(n%2==0):
        n=n//2
        if(2 in d):
            d[2]+=1
        else:
            d[2]=1
    for i in range(3,int(n**0.5)+1):
        while(n%i==0):
            n=n//i
            if(i in d):
                d[i]+=1
            else:
                d[i]=1
    if(n>1):
      d[n]=1
      if(n==c):
          return 1
    su=0
    for i in d:
        f=d[i]*2
        su+=(-1+(int((1+4*f)**0.5)))//(2)
    return su
            
n=int(input())
c=n
print(div(c,n))

Measured memory_bytes: 63492
import math
X = int(input())
c = 0
N = True
while N:
  for i in range(2,math.ceil((X+c)**.5)+1):
    if (X+c)%i == 0:
      c += 1
      break
  else:
    N = False 
print(X+c if X>2 else 2)

Measured memory_bytes: 9396
import sys
N = int(input())
A = list(map(int,input().split()))
for i in range(N):
  if A[i] % 2 == 0:
    if A[i] % 3 == 0 or A[i] % 5 == 0:
      None
    else:
      print("DENIED")
      sys.exit()
print("APPROVED")

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

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

int N;
int x,y,z;

int main(){
	scanf("%d" , &N);
	repp(i,0,N){
		int a;
		scanf("%d" , &a);
		if(a % 4 == 0) ++z;
		else if(a % 2 == 0) ++y;
		else ++x;
	}
	printf("%s\n" , (z + y/2) >= N/2 ? "Yes" : "No");
	return 0;
}


Measured memory_bytes: 256
using static System.Console;

class Program
{
    static void Main(string[] args)
    {
        int a = int.Parse(ReadLine());
        int b = int.Parse(ReadLine());
        int c = int.Parse(ReadLine());
        int x = int.Parse(ReadLine());
        int count = 0;
        for (int i = 0; i <= a; i++)
        {
            for (int j = 0; j <= b; j++)
            {
                for (int k = 0; k <= c; k++)
                {
                    if (500 * i + 100 * j + 50 * k == x) count++;
                }
            }
        }
        WriteLine(count);
    }
}

Measured memory_bytes: 13140
#include <bits/stdc++.h>
#define int long long

using namespace std;

int n=0,k=0;
int a[200001];
int s[200001];
map<int, int> Map;

signed main()
{
	cin >> n >> k;
	for (int i=1; i<=n; i++)
	{
		cin >> a[i];
	}
	s[0] = 0;
	for (int i=1; i<=n; i++)
	{
		s[i] = s[i-1]+a[i];
	}
	Map[0]++;
	int res=0;
	for (int i=1; i<=n; i++)
	{
		if (i-k>=0)	
		{
			Map[(s[i-k]-(i-k))%k]--;		
		}	
		res+=Map[(s[i]-i)%k];
		Map[(s[i]-i)%k]++;	
	}		
	cout << res;
	return 0;
}


Measured memory_bytes: 15872
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
#define rep(i, n) for (int i = 0, i##_len = (int)(n); i < i##_len; i++)
#define ALL(v) (v).begin(), (v).end()
#define PUTS(x) cout << (x) << endl;
vector<Int> IntsIn(int n) {
    auto v = vector<Int>(0);
    for (int i = 0; i < n; i++) {
        Int a;
        cin >> a;
        v.push_back(a);
    }
    return v;
}

int main() {
    Int h;
    cin >> h;
    Int ans = 0;
    Int current = 1;
    while (h > 0) {
        ans += current;
        current *= 2;
        h /= 2;
    }
    PUTS(ans);
}


Measured memory_bytes: 256
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
#include <functional>
#include <cassert>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)
#define ALL(v) v.begin(),v.end()
template < class T > inline bool chmax(T& a, T b) {if (a < b) { a=b; return true; } return false; }
template < class T > inline bool chmin(T& a, T b) {if (a > b) { a=b; return true; } return false; }
#define DEBUG_VLL(vec) REP(sz, vec.size()) std::cerr<<vec[sz]<<(sz==vec.size()-1?'\n':' ');

const long long MOD = 1000000007;
const long long HIGHINF = (long long)1e18;
const int INF = (int)1e9;

int n, m;
V< P< P<int, int>, ll> > edges;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    edges.resize(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        ll c;
        cin >> a >> b >> c;
        edges.emplace_back(make_pair(a - 1, b - 1), -c);
    }

    vll dist(n, HIGHINF);
    dist[0] = 0;
    for (int i = 0; i < n; i++) {
        for (P< P<int, int>, ll> e: edges) {
            if (dist[e.first.second] > dist[e.first.first] + e.second) dist[e.first.second] = dist[e.first.first] + e.second;
        }
    }

    V<int> loop(n, 0);
    for (int i = 0; i < n; i++) {
        for (P< P<int, int>, ll> e: edges) {
            if (dist[e.first.second] > dist[e.first.first] + e.second) {
                dist[e.first.second] = dist[e.first.first] + e.second;
                loop[e.first.second] = 1;
            }
            if (loop[e.first.first] == 1)  loop[e.first.second] = 1;
        }
    }

    if (loop[n - 1] == 1) cout << "inf\n";
    else cout << -dist[n - 1] << '\n';
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T, class U> using Pa = pair<T, U>;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,K;
    cin >> N >> K;
    vec<ll> A(N),B(N);
    for(int i=0;i<N;i++) cin >> A[i] >> B[i];
    ll ans = 0;
    vec<int> use(N,1);
    int h = 0;
    for(int i=0;i<30;i++) if(K>>i&1) h = i;
    for(int i=0;i<N;i++){
        int a = 0;
        for(int j=0;j<30;j++) if(A[i]>>j&1) a = j;
        if(a>h) use[i] = 0;
    }
    for(int k=h;k>=0;k--){
        ll now = 0;
        if(K>>k&1){
            for(int i=0;i<N;i++) if(use[i]){
                if(!(A[i]>>k&1)) now += B[i];
            }
        }
        if(!(K>>k&1)){
            for(int i=0;i<N;i++){
                if(A[i]>>k&1) use[i] = 0;
            }
        }
//        cerr << k << " " << ans << "\n";
        ans = max(ans,now);
    }
    ll s = 0;
    for(int i=0;i<N;i++) if(use[i]) s += B[i];
    ans = max(ans,s);
    cout << ans << "\n";
}

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

int main() {
  int A, B, C, D, E, F;
  cin >> A >> B >> C >> D >> E >> F;

  vector<int> waters;
  for (int i = 0; i <= 30; i++) {
    for (int j = 0; j <= 30; j++) {
      int water = 100 * A * i + 100 * B * j;
      if (water <= F) {
        waters.push_back(water);
      }
    }
  }

  vector<int> sugars;
  for (int i = 0; i <= 3000; i++) {
    for (int j = 0; j <= 3000; j++) {
      int sugar = C * i + D * j;
      if (sugar <= F) {
        sugars.push_back(sugar);
      }
    }
  }

  int ans_w = 0;
  int ans_s = 0;
  double percent = -1e20;

  for (auto w : waters) {
    for (auto s : sugars) {
      int total = w + s;
      if (total > F) {
        continue;
      }

      int sugar_upper_limit = (w / 100) * E;

      double p = double(100 * s) / double(w + s);
      if (s <= sugar_upper_limit && p > percent) {
        ans_w = w;
        ans_s = s;
        percent = p;
      }
    }
  }

  cout << (ans_w + ans_s) << " " << ans_s << endl;
  return 0;
}

Measured memory_bytes: 1400
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// #define int long long
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPS(i, r, n) for (int i = (r); i < (n); ++i)
#define REPR(i, n) for(int i = (n); i >= 0; --i) // from n to 0
#define REPRS(i, r, n) for(int i = (n); i >= (r); --i) // from n to r
#define REPOBJ(itr, obj) for(auto itr = (obj).begin(); itr != (obj).end() ; ++itr)
#define REPROBJ(itr, obj) for(auto itr = (obj).rbegin(), e = (obj).rend(); itr != e; ++itr)
#define COUTB(x) cout << (x) << "\n"
#define COUTS(x) cout << (x) << " "
#define PB push_back
#define SORT(obj) sort((obj).begin(), (obj).end())
#define SORTR(obj) sort((obj).begin(), (obj).end(), greater<>())
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define PI (acos(-1))

int lcm(int, int);
map<int,int> GetPrimeFactors(int);
bool IsPrime(int);
int Factorial(int);
int npr (int, int);
int ncr (int, int);

/***** MAIN *****/
void Main() {
  int n;
  cin >> n;
  int ans = ceil((double)n/2);
  cout << ans;
  cout << "\n";
}
/***** MAIN *****/

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  Main();
  return 0;
}

int lcm(int a, int b) { return a / __gcd(a,b) * b;}

map<int,int> GetPrimeFactors(int n) {
  map<int,int> mp;
  // dived by 2, 3, 5, ...
  for(int i=2; i*i<=n; i+=2) {
    if(i==4) i = 3;
    while(n%i == 0) {
      ++mp[i];
      n /= i;
    }
  }
  if(n!=1) ++mp[n];

  return mp;
}

bool IsPrime(int a) {
  if(a <= 1) return false;
  if(a == 2) return true;
  if(a%2 == 0) return false;
  for(int i = 3; i*i <= a; i+=2) {
    if(a%i==0) return false;
  }
  return true;
}

int Factorial(int n){
  int ans = 1;
  while(n > 1){
    ans *= n;
    --n;
  }
  return ans;
}

int npr(int n, int r) {
  return Factorial(n)/Factorial(n-r);
}

int ncr (int n, int r){
  return npr(n,r)/Factorial(r);
}


Measured memory_bytes: 256