akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

int main(){
  int n,k,c;
  cin >> n >> k >> c;
  string str;
  cin >> str;
  
  //cout << n << endl;
  int L[k], R[k];

  int p=0, num=0;

  while(num<k){
    if(str[p]=='o'){
      L[num] = p;
      //cout << p << endl;
      p+=c;
      num++;
      
    }
    p++;
  }
  
  num = k-1;
  p=n-1;
  while(num>=0){
    if(str[p]=='o'){
      R[num] = p;
      //cout << p << endl;
      p-=c;
      num--;
    }
    p--;
  }

  for(int i=0; i<k; i++){
    //cout << L[i] << " " << R[i] << endl;
    if(L[i]==R[i]){
      cout << L[i]+1 << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 3332
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <string>

using namespace std;

int n, a, b;

int main() {
	cin >> n >> a >> b;
	if((b - a) % 2) puts("Borys");
	else puts("Alice");
	return 0;	
}

Measured memory_bytes: 256
'''
import math

def gcd (a,b):
    if (b == 0):
        return a
    else:
        return gcd(b, a % b)

def gcd_list(arr):

    ans = arr[0]
    for c in arr[1::]:
        ans = gcd(ans , c)
    return ans
'''
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

N = int(input())

A = list(map(int, input().split()))
A.sort()

af = A[0]
ag = A[1]

F = make_divisors(af)
G = make_divisors(ag)
F.sort(reverse=True)
G.sort(reverse=True)
del F[-1]
del G[-1]

'''
print(F)
print(G)
'''

ansf = 1
ansg = 1

for i in F:
    count = 0
    for j in A:
        if j % i != 0:
            count += 1
            if count == 2:
                break

    if count == 1:
        ansf = i
        break
    if count == 0:
        ansf = i
        break

for i in G:
    count = 0
    for j in A:
        if j % i != 0:
            count += 1
            if count == 2:
                break

    if count == 1:
        ansg = i
        break

print(max(ansf,ansg))
'''
g = gcd_list(A)
print(g)

for i in range(N):
    tmp = A.pop(0)
    if g < gcd_list(A):
        g = gcd_list(A)
    A.append(tmp)

print(g)
'''

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

int main() {
    int N, M;
    int min_dist = 0;

    cin >> N >> M;
    if (M <= N) { cout << min_dist << endl;  return 0; }

    int X[M], x_dist[M-1];
    int x_dist_size = sizeof(x_dist) / sizeof(*x_dist);

    for (int i=0; i<M; i++) { cin >> X[i]; }
    sort(X, X + M);

    for (int i=0; i<x_dist_size; i++) { x_dist[i] = X[i+1] - X[i]; }
    sort(x_dist, x_dist + x_dist_size, greater<int>());

    int skip = N - 1;
    for (int i=skip; i<x_dist_size; i++) {
        min_dist += x_dist[i];
    }
    cout << min_dist << endl;
    return 0;
}

Measured memory_bytes: 1024
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<string.h>
int main()
{
	int n;
	while(~scanf("%d",&n))
	{
		int z[100]={0};
		int total=0;
		for(int i=0;i<n;i++)
		scanf("%d",&z[i]);
		for(int i=1;i<n-1;i++)
		{
			if(z[i]>z[i-1]&&z[i]<z[i+1]||z[i]<z[i-1]&&z[i]>z[i+1])
			total++;
		}
		printf("%d\n",total);
	}
}

Measured memory_bytes: 256
a, b, c, x, y = gets.chomp.split.map(&:to_i)
  
max = [x, y].max

minp = 100000000000

(0..max).each do |i|
  pa = [0, x - i].max * a
  pb = [0, y - i].max * b
  pab = 2 * i * c
  p = pa + pb + pab
  if p < minp
    minp = p
  end
end

puts(minp)

Measured memory_bytes: 1788
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 c = sc.nextInt();
        int tmp = c-a-b;
        long tmp2 = (long)tmp*tmp;
        long tmp3 = (long)4 * a * b;
        if (tmp > 0 && tmp2 > tmp3) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }

    }
}

Measured memory_bytes: 23636
# import bisect
from collections import Counter, deque
# from copy import copy, deepcopy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
# from operator import xor
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline

def resolve():

    N=int(input())
    A=sorted(list(map(int,input().split())),reverse=True)
    temp=-1
    maxans=0
    AA=Counter(A)
    for (i,j) in AA.items():
        if j>=4:
            maxans=max(i**2,maxans)
        if j>=2:
            if temp>=0:
                maxans=max(maxans,temp*i)
            temp=max(i,temp)
    print(maxans)




resolve()

Measured memory_bytes: 69912
import math

#成績xを取れるか？xに関して二分探索

N,K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))

#Aを小さい順，Fを大きい順に並べれば対応する．
A.sort()
F.sort(reverse =True)
AF=[0]*N

for i in range(N):
    AF[i]=A[i]*F[i]
    
ng=-1
ok=10**12+1

#二分探索，成績xをとるのにi番目の人が何回修行すべきか，これがK以下なら良い
while ok-ng!=1:
    x = (ok+ng)//2
    num_tra =0
    for i in range(N):
        af_i = int(math.ceil((AF[i]-x)/F[i]))
        if af_i>0:
            num_tra+=af_i
    if num_tra<=K:
        ok=x
    else:
        ng=x
        
print(ok)

Measured memory_bytes: 119756
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string str;
  cin >> str;
  int x = str.size() -1;
 
  if( str.at(x) == 's' ){
    cout << str + "es" << endl;
  }
  else {
    cout << str + "s" << endl;
  }
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
#define int           long long
#define pb            push_back
#define x             first
#define y             second
#define sz(v)         (int)v.size()
#define all(x)        (x).begin(),(x).end()
#define PI            3.14159265358979
#define N             200005

int solve(){
    int n; cin>>n;
    int a[n];
    for (int i = 0; i < n; ++i)
    {
        cin>>a[i];
        if(!a[i]){
            cout<<0;
            return 0;
        }
    }
    int m=1e18,ans=1;
    for (int i = 0; i < n; ++i)
    {
        if(m/ans<a[i]){
            cout<<-1;
            return 0;
        }
        ans*=a[i];
    }
    cout<<ans;
    return 0;
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int t=1;
    // cin>>t;
    while(t--) solve();
    return 0;
}

Measured memory_bytes: 4436
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
#include <tuple>


using namespace std;

int main(){

	int A[3];

	cin >> A[0] >> A[1] >> A[2];

	sort(A, A+3);

	cout << A[2] * 10 + A[1] + A[0] << endl;

	return 0;
}


Measured memory_bytes: 256
import numpy as np

# A,B = list(map(int, input().split()))

# N = int(input())
N,M = list(map(int, input().split()))
As = np.array(list(map(int, input().split())))

# As.sort(reverse=True)
As[::-1].sort()
max_A = As[0]

while M > 0:
    i=1
    for i in range(1, min(M, N)):
        if As[i] <= max_A//2:
            break
    # print(M)
    # print(As)
    # print(i)
    As[:min(M,i)] = As[:min(M,i)] // 2
    # print(As)
    M -= i
    As[::-1].sort()
    max_A = As[0]
    # print(As)

print(np.sum(As))


Measured memory_bytes: 23100
import java.util.Scanner;

public class Main
{

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

		int a = Integer.parseInt(sc.next());
		int b = Integer.parseInt(sc.next());
		int answer = (a - b > 0) ? a + (a - 1) :
					 (b - a > 0) ? b + (b - 1) :
						 		   a + b;

		System.out.println(answer);
		sc.close();
	}
}

Measured memory_bytes: 21716
import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
import std.range;
import std.container;
 
void main(){
    auto arr = readln.chomp.split.map!(to!int).array;
    int a = arr[0], b = arr[1];
    auto s = readln.chomp;
    auto t = readln.chomp;
    auto dp = new int[][][](2, a+2, b+2);
    foreach(i; 0..a+1) foreach(j; 0..b+1) dp[0][i][j] = dp[1][i][j] = int.min;
    foreach(i; 0..a+1){
        foreach(j; 0..b+1){
            if(i != a){
                if(s[i] == 'I') dp[1][i+1][j] = max(dp[1][i+1][j], dp[0][i][j] + 1, 1);
                else            dp[0][i+1][j] = max(dp[0][i+1][j], dp[1][i][j] + 1);
            }
            if(j != b){
                if(t[j] == 'I') dp[1][i][j+1] = max(dp[1][i][j+1], dp[0][i][j] + 1, 1);
                else            dp[0][i][j+1] = max(dp[0][i][j+1], dp[1][i][j] + 1);
            }
        }
    }
    int ans = int.min;
    foreach(i; 0..a+2) foreach(j; 0..b+2) ans = max(ans, dp[1][i][j]);
    writeln(ans);
}

Measured memory_bytes: 34292
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<stdbool.h>
typedef long long ll;
typedef long double ld;
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define rrep(i,l,r)for(ll i=(l);i>=(r);i--)
#define INF (1LL<<60)
#define MOD1 1000000007
#define MOD2 998244353
#define MAX_N (1 << 17)
#define YES printf("Yes\n")
#define NO printf("No\n")
#define PN printf("\n")

void swap(ll *a, ll *b){ll c;c=*b;*b=*a;*a=c;}
ll max2(ll a,ll b){return a>=b?a:b;}
ll min2(ll a,ll b){return a>=b?b:a;}
ll min3(ll a, ll b, ll c){return (a<=b && a<=c) ? a : b<=c ? b : c;}
ll max3(ll a, ll b, ll c){return (a>=b && a>=c) ? a : b>=c ? b : c;}
ll minn(ll n, ll a[n]){ll b=INF;rep(i,0,n) b=min2(b,a[i]);return b;}
ll maxn(ll n, ll a[n]){ll b=-INF;rep(i,0,n) b=max2(b,a[i]);return b;}
ll ABS(ll a){return a>=0?a:(-a);}
ll POW(ll a, ll b){ll c=1;rep(i,0,b) c*=a;return c;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll mod(ll n){n+= n<0?((-n)/MOD1+1)*MOD1:0; return n%=MOD1;}
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}

typedef struct{ ll a , b;}fr;
int cmp1( const void *p, const void *q ) { return ((fr*)p) ->a - ((fr*)q)->a;}
int cmp2( const void *p, const void *q ) { return ((fr*)q) ->a - ((fr*)p)->a;}
void strsortup(fr*a,int n){qsort(a,n,sizeof(fr),cmp1);}
void strsortdown(fr*a,int n){qsort(a,n,sizeof(fr),cmp2);}

/*-------------------------------------------------*/
// Union Find              添字に注意!!!!!!!!!!
typedef struct{
    ll num; //number
    ll par; //parent
    ll height; //height
}UF;
void UFmake(ll n, UF b[n]){for(ll i=0;i<n;i++){
    b[i].par = i;
    b[i].num = i;
    b[i].height = 1;
    }
}
ll UFroot(ll n, ll a,UF b[n]){ return a==b[a].par?a:UFroot(n,b[a].par,b); }
void UFunite(ll n, ll x, ll y, UF b[n]){
    if(b[UFroot(n,x,b)].height > b[UFroot(n,y,b)].height) b[UFroot(n,y,b)].par = UFroot(n,x,b);
    else{ b[UFroot(n,x,b)].par = UFroot(n,y,b); b[UFroot(n,y,b)].height = max2(b[UFroot(n,y,b)].height,b[UFroot(n,x,b)].height+1);}
}
ll UFsame(ll n, ll x, ll y, UF b[n]){ return UFroot(n,x,b) == UFroot(n,y,b) ? 1 : 0; }

/*-------------------------------------------------------------*/

int main(void){
    // char ;
    ll n,m,ans=0;
    scanf("%lld%lld",&n,&m);
    ll p[n],x,y;
    rep(i,0,n){
        scanf("%lld",&p[i]);
    }
    UF seq[n];
    UFmake(n,seq);
    rep(i,0,m){
        scanf("%lld%lld",&x,&y);
        UFunite(n,x-1,y-1,seq);
    }
    rep(i,0,n){
        if( UFsame(n,i,p[i]-1,seq) ){
            ans++;
        }
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 3328
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <utility>
#include <set>
#include <tuple>

int main() {
  size_t N;
  scanf("%zu", &N);

  std::vector<intmax_t> H(N);
  for (auto& hi: H) scanf("%jd", &hi);

  if (N == 1) return puts("Yes"), 0;

  --H[0];
  for (size_t i = 1; i < N; ++i) {
    if (H[i-1] < H[i]) {
      --H[i];
    } else if (H[i-1] == H[i]) {
    } else if (H[i-1] > H[i]) {
      return puts("No"), 0;
    }
  }

  puts(std::is_sorted(H.begin(), H.end())? "Yes": "No");
}


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

const ll INF = 1001001001;

int main(){
    ll N; cin >> N;
    ll h;
    for(ll n = 1; n <= 3500; n++){
        for(ll w = n; w <= 3500; w++){
            ll tmp = (4 * n * w - N * w - N * n);
            ll top = n * w * N;
            if(tmp > 0 && top > 0 && top % tmp == 0){
                h = top / tmp;
                if(h > 0){
                    cout << h << " " << n << " " << w << endl;
                    return 0;
                }
            }
        }
    }
}


Measured memory_bytes: 3672
#include<bits/stdc++.h>
#define rep(i,n) for (long long i = 0; i < (n); ++i)
//g++ -std=c++11 

#define DIV 998244353

using namespace std;

long long N;
vector<pair<long long, long long> >XD;

vector<long long> tree[200005];

long long dfs(long long cur) {
	long long ret = 1;
	for(long long next: tree[cur]) {
		ret *=	dfs(next);
		ret %= DIV;
	}
	//全部xにするやつ
	ret++;
	return ret;
}

int main(){
	cin >> N;
	rep(i, N) {
		long long x, d;
		cin >> x >> d;
		XD.push_back(make_pair(x, d));
	}
	// X, D
	sort(XD.begin(), XD.end(), greater<pair<long long, long long> >());

	// X, idx
	stack<pair<long long, long long> > memo;

	rep(i, N) {
		long long X = XD[i].first;
		long long D = XD[i].second;

		while(memo.size() > 0 && memo.top().first < X+D) {
			tree[i].push_back(memo.top().second);
			memo.pop();
		}
		memo.push(make_pair(X, i));
	}

	long long ans = 1;
	while(!memo.empty()) {
		long long idx = memo.top().second;
		memo.pop();
		ans *= dfs(idx);
		ans %= DIV;
	}
	cout << ans << endl;
}


Measured memory_bytes: 26516
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define FORR(i, a, b) for (int i = b - 1; i >= a; --i)
#define SORT(v) sort(v.begin(), v.end())
#define SORTR(v) sort(v.rbegin(), v.rend())
#define REV(v) reverse(v.begin(), v.end())
#define ITER(itr, v) for (auto itr = v.begin(); itr != v.end(); ++itr)
#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 SZ(v) (int)v.size()
using namespace std;
using ll = long long;
using P = pair<int, int>;

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

	string S, T;
	cin >> S >> T;
	int n = SZ(S);
	if (T.substr(0, n) == S)
		cout << "Yes\n";
	else
		cout << "No\n";

	return 0;
}

Measured memory_bytes: 3640
import java.util.Scanner;
import java.util.Stack;

class Main {
  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    Stack<Integer> cars = new Stack<Integer>();

    while (sc.hasNext()) {
      int carNum = sc.nextInt();

      if (carNum == 0) {
        System.out.println(cars.pop());
      } else {
        cars.push(carNum);
      }
    }
  }
}

Measured memory_bytes: 17200
#include <algorithm>
#include <iostream>
#include<string>
#include<vector>
#include <numeric>
#include <queue>
using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;
	vector<long> a(n);
	priority_queue<long> q;

	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	for (int i = 0; i < n; i++)
	{
		q.push(a[i]);
	}

	while (m>0)
	{
		long a = q.top();
		a /= 2;
		q.pop();
		q.push(a);
		m--;
	}
	long long ans = 0;
	for (int i = 0; i < n; i++)
	{
		ans += q.top();
		q.pop();
	}
	cout << ans << endl;
}

Measured memory_bytes: 2168
from sys import exit
n = int(input())
powlist = set()
k = 2
chance = True
if n == 1:
    print(1)
    exit()
while chance:
    for i in range(1, n):
        key = i**k
        if key <= n:
            powlist.add(key)
        else:
            k += 1
            judge = i
            break
    if judge == 2:
        chance = False
print(max(powlist))

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

using namespace std;

struct square {
    int x, y;
};

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

int main() {

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

    while(cin >> N, N) {

        int n, d;
        int min_x, min_y;
        int max_x, max_y;
        square s[N];

        min_x = min_y = 0;
        max_x = max_y = 0;
        s[0].x = s[0].y = 0;

        for(int i = 1; i < N; ++i) {
            cin >> n >> d;
            s[i].x = s[n].x + dx[d];
            s[i].y = s[n].y + dy[d];
            min_x = min(min_x, s[i].x);
            min_y = min(min_y, s[i].y);
            max_x = max(max_x, s[i].x);
            max_y = max(max_y, s[i].y);
        }

        cout << max_x - min_x + 1 << " " << max_y - min_y + 1 << endl;

    }

}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    string s, trim;
    vector<int> pos; 
    
    cin >> s;
    int n = s.size();
    for (int i = 0; i < n; ++i) {
        if (s[i] != 'x') {
            trim += s[i];
            pos.push_back(i);
        }
    }
   if (trim.empty()) { cout << 0 << endl; return 0;}

 
    string rtrim = trim;
    reverse(rtrim.begin(), rtrim.end());
    if (trim != rtrim) {
        cout << -1 << endl;
    } else {
        int len = trim.size();
        int p1 = pos[(len - 1) / 2], p2 = pos[len / 2];
 
        int ans = 0;
        while (p1 >= 0 or p2 < n) {
            if (p1 >= 0 and p2 < n and s[p1] == s[p2]) {
                --p1; ++p2; continue;
            }
            if (p1 >= 0 and p2 < n and s[p1] != s[p2]) {
                assert(s[p1] == 'x' or s[p2] == 'x');
                ans += 1;
                if (s[p1] == 'x') --p1;
                else ++p2;
                continue;
            }
            
            ans += 1;
            if (p1 >= 0) --p1;
            else ++p2; 
        }    
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 1148
/** 	Author: Apoorva Mittal  **/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define nl "\n"
#define vi vector<int>
#define vvi vector<vector<int>>
#define vii vector<pair<int, int>>
#define rep(i, a, b) for (int i = a; i < b; i++)
#define repD(i, a, b) for (int i = a; i >= b; i--)
#define speed                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0)
#define init(i, k) memset(i, k, sizeof i)
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define inp(a) rep(i, 0, a.size()) cin >> a[i];
#define out(a)                               \
    cout << #a << ": " << endl;              \
    rep(i, 0, a.size()) cout << a[i] << " "; \
    cout << endl;
#define out2d(a)                \
    cout << #a << ": " << endl; \
    rep(i, 0, a.size())         \
    {                           \
        rep(j, 0, a[0].size())  \
                cout            \
            << a[i][j] << " ";  \
        cout << endl;           \
    }
#define flush fflush(stdout);
#define lb lower_bound
#define ub upper_bound
#define maxe *max_element
#define mine *min_element
#define umap unordered_map
#define uset unordered_set
#define mset multiset
#define pqueue priority_queue
#define precise(x) cout << fixed << showpoint << setprecision(x);
#define setbit(x) __builtin_popcountll(x)
#define gcd(a, b) __gcd(a, b)
#define deb(x) cout << #x << " " << x << endl;
#define Y "YES"
#define N "NO"
const int mod = 1e9 + 7;
// ====== Useful functions begin ======
inline int add(int a, int b) { return ((a % mod) + (b % mod)) % mod; }
inline int sub(int a, int b) { return ((a % mod) - (b % mod) + mod) % mod; }
inline int mul(int a, int b) { return ((a % mod) * (b % mod)) % mod; }
// ====== Useful functions end ======
const int inf = 1e18;
const int maxn = 1e3 + 5;

//--------------------------------------------------------------------------------------------------------------------------------

//--------------------------------------------------------------------------------------------------------------------------------
void max_self(int &a, int b)
{
    a = max(a, b);
}
void solve()
{
    int n, W;
    cin >> n >> W;
    vi dp(W + 1, 0);

    for (int i = 0; i < n; i++)
    {
        int w, v;
        cin >> w >> v;
        for (int wa = W - w; wa >= 0; wa--)
        {
            max_self(dp[wa + w], v + dp[wa]);
        }
        // out(dp)
    }
    cout<<dp[W]<<endl;
}
signed main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    speed;
    int t = 1;
    // cin >> t;

    for (int tt = 1; tt <= t; tt++)
    {
        // cout<<"Case #"<<tt<<": ";
        solve();
    }
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
using namespace std;
int a[100005];
int main() {
    int n;
    scanf("%d",&n);
    for (int i=1; i<=n; i++) {
        scanf("%d",&a[i]);
    }
    long long Max=2,Min=2;
    for(int i=n;i>=1;i--)
    {
        if(Min%a[i]!=0)
        Min=Min/a[i]*a[i]+a[i];
        Max=Max/a[i]*a[i]+a[i]-1;
        if(Min>Max)
        {
            puts("-1");
            return 0;
        }
    }
    printf("%lld %lld\n", Min, Max);
    return 0;
}

Measured memory_bytes: 640
/*
confirm 0LL and 1LL
confirm cornercases such as 0
confirm times of cin < 10^6
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Pld = pair<ld, ld>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
using VecC = vector<char>;
using VecD = vector<ld>;
using VecS = vector<string>;
using Graph = vector<VecP>;
template <typename T>
using Vec1 = vector<T>;
template <typename T>
using Vec2 = vector<Vec1<T> >;
#define REP(i, m, n) for(ll (i) = (m); (i) < (n); ++(i))
#define REPN(i, m, n) for(ll (i) = (m); (i) <= (n); ++(i))
#define REPR(i, m, n) for(ll (i) = (m)-1; (i) >= (n); --(i))
#define REPNR(i, m, n) for(ll (i) = (m); (i) >= (n); --(i))
#define rep(i, n) REP(i, 0, n)
#define repn(i, n) REPN(i, 1, n)
#define repr(i, n) REPR(i, n, 0)
#define repnr(i, n) REPNR(i, n, 1)
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define fs first
#define sc second
template <typename T>
bool chmax(T &a, const T b){if(a < b){a = b; return true;} return false;}
template <typename T>
bool chmin(T &a, const T b){if(a > b){a = b; return true;} return false;}
template <typename T>
ll pow2(const T n){return (1LL << n);}
template <typename T>
void cosp(const T n){cout << n << ' ';}
void co(void){cout << '\n';}
template <typename T>
void co(const T n){cout << n << '\n';}
template <typename T1, typename T2>
void co(pair<T1, T2> p){cout << p.fs << ' ' << p.sc << '\n';}
template <typename T>
void co(const Vec1<T> &v){for(T i : v) cosp(i); co();}
template <typename T>
void co(initializer_list<T> v){for(T i : v) cosp(i); co();}
template <typename T>
void ce(const T n){cerr << n << endl;}
template <typename T>
void ce(initializer_list<T> v){for(T i : v) cerr << i << ' '; cout << endl;}
void sonic(){ios::sync_with_stdio(false); cin.tie(0);}
void setp(const ll n){cout << fixed << setprecision(n);}
constexpr int INF = 1e9+1;
constexpr ll LINF = 1e18+1;
constexpr ll MOD = 1e9+7;
//constexpr ll MOD = 998244353;
constexpr ld EPS = 1e-11;
const ld PI = acos(-1);

ll cnt[500][500];

int main(void){
	ll n, m, q;
	cin >> n >> m >> q;
	rep(i, m){
		ll l, r;
		cin >> l >> r;
		l--, r--;
		cnt[l][r]++;
	}

	rep(i, n){
		rep(j, n){
			if(j == 0) continue;
			cnt[i][j] += cnt[i][j - 1];
		}
	}

	rep(i, q){
		ll l, r;
		cin >> l >> r;
		l--, r--;
		ll ans = 0;
		REPN(i, l, r) ans += cnt[i][r];
		co(ans);
	}

	return 0;
}


Measured memory_bytes: 2816
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define PI acos(-1)
#define pcnt __builtin_popcountll
#define rng(a) a.begin(), a.end()
#define sz(x) (int)(x).size()
#define v(T) vector<T>
#define vv(T) v(v(T))

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;

template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
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; }

ll INF = 1001001001;
ll LINF = 1001001001001001001ll;

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

    ll n;
    cin>>n;
    bool all = true;
    rep(i, n) {
        ll a;
        cin>>a;
        if (a % 2) all = false;
    }
    if (all) cout<<"second"<<endl;
    else cout<<"first"<<endl;
}

Measured memory_bytes: 256
// Ver19.03
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INF (1 << 29) * 2
#define LLINF 4545454545454545454
#define MOD 1000000007
#define ll long long
#define ull unsigned long long
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
int upll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? -1 : *(ll *)a > *(ll *)b ? 1 : 0; }
int downll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? 1 : *(ll *)a > *(ll *)b ? -1 : 0; }
void sortup(ll *a, int n) { qsort(a, n, sizeof(ll), upll); }
void sortdown(ll *a, int n) { qsort(a, n, sizeof(ll), downll); }

int main()
{
  int a, b, flag;
  scanf("%d%d", &a, &b);
  if (a == b)
    flag = 0;
  else if (a > b || a == 1)
    if (b == 1)
      flag = -1;
    else
      flag = 1;
  else
    flag = -1;
  puts(flag == 1 ? "Alice" : flag ? "Bob" : "Draw");
  return 0;
}

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

int main()
{
    long long A, B;
    cin >> A >> B;

    for (int i = 1; i <= B; i++) {
        if ((A * i) % B == 0) {
            cout << (A * i) << endl;
            break;
        }
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
	int x; cin >> x;
	int ans = 1;
	for (int i = 2; i <= x; ++i) {
		int tmp = i * i;
		while (tmp <= x) {
			ans = max(ans, tmp);
			tmp *= i;
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
import collections
N = int(input())
A = list(map(int, input().split()))

L = []
R = []

ans = 0

for i in range(N):
    L.append(i + A[i])
    R.append(i - A[i])

r = collections.Counter(R)

for l in L:
    ans += r[l]

print(ans)



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

#define PB          push_back
#define PF          push_front
#define MP          make_pair
#define FI          first
#define SE          second
#define SIZE( A )   int( ( A ).size( ) )
#define ALL( A )    ( A ).begin( ), ( A ).end( )
#define ALLR( A )   ( A ).rbegin( ), ( A ).rend( )

using namespace std;

typedef long long           ll;
typedef unsigned long long  ull;
typedef long double         lf;
typedef pair< int, int >    pii;
typedef pair< ll, ll >      pll;
typedef vector< bool >      vb;
typedef vector< lf >        vd;
typedef vector< ll >        vll;
typedef vector< int >       vi;
typedef vector< pii >       vpii;

const int MAXN = int( 1e5 )+10;
const int MOD  = int( 360 );
const int oo   = INT_MAX;
const lf EPS = 1e-9;

struct pt {
  lf x, y;
  pt( ) { }
  pt( lf x, lf y ) : x( x ), y ( y ) { }
};

inline lf x( pt P ) { return P.x; }
inline lf y( pt P ) { return P.y; }

istream& operator >> ( istream& in, pt& p ) {
  lf x,y; in >> x >> y;
  p = pt(x,y); return in;
}

ostream& operator << ( ostream& out, const pt& p ) {
  out << double(p.x) << " " << double(p.y);
  return out;
}

pt operator + ( const pt& A, const pt& B ) {
  return pt( x(A)+x(B), y(A)+y(B) );
}

pt operator - ( const pt& A, const pt& B ) {
  return pt( x(A)-x(B), y(A)-y(B) );
}

pt operator * ( const lf& B, const pt& A ) {
  return pt( x(A)*B, y(A)*B );
}

pt operator * ( const pt& A, const lf& B ) {
  return pt( x(A)*B, y(A)*B  );
}

inline lf norm( pt A ) {
  return x(A)*x(A) + y(A)*y(A);
}

inline lf abs( pt A ) {
  return sqrt( norm(A) );
}

inline bool same ( lf a, lf b ) {
  return a+EPS > b && b+EPS > a;
}

inline lf dist ( pt A, pt B ) { return norm( B - A ); }

int n;
pt P[ MAXN ], extra[ MAXN ];
lf d;

bool cmpX( const pt &A, const pt &B ) {
  return A.x+EPS < B.x;
}

lf sqr( lf x ) {
  return x*x;
}

void merge( int f, int m, int t ){
	int total = t - f + 1;
	for( int i = 0, l = f, r = m+1; i < total; ++i ){
		if( l == m+1 ){
      extra[ i ] = P[ r++ ];
		}
		else if( r == t+1 ){
		  extra[ i ] = P[ l++ ];
		}
		else if( P[l].y+EPS < P[r].y ){
		  extra[ i ] = P[ l++ ];
		}
		else{
		  extra[ i ] = P[ r++ ];
		}
	}
	for( int i = 0; i < total; ++i ){
    P[ f+i ] = extra[ i ];
	}
}

void solve( int f, int t ) {
  if( f == t ) return;
	int mi = (f + t)/2;
	lf mx = P[ mi ].x;
	solve( f, mi );
  solve( mi+1, t );
	merge( f, mi, t );
	vector< int > idxs;
	for( int i = f; i <= t; ++i ){
		if( sqr(mx - P[i].x) < d+EPS ) idxs.push_back( i );
	}
	for( int i = 0; i < idxs.size(); ++i ){
		for( int j = i+1; j < idxs.size() && sqr(P[ idxs[i] ].y - P[ idxs[j] ].y) < d+EPS; ++j ){
			d = min( d, dist( P[ idxs[i] ], P[ idxs[j] ] ) );
		}
	}
}

int main( ) {

  #ifdef LOCAL
    freopen( "CGL_5_A-in25.txt", "r", stdin );
    //freopen( "output", "w", stdout );
  #else
    //freopen( "input", "r", stdin );
    //freopen( "output", "w", stdout );
    ios_base::sync_with_stdio( 0 );
    cin.tie( 0 );
  #endif
  cout << fixed << setprecision( 10 );
  cin >> n;
  for( int i = 0; i < n; ++i ) {
    cin >> P[i];
  }
  sort( P, P+n, cmpX );
  d = oo;
  solve( 0, n-1 );
  cout << double( sqrt(d) ) << '\n';
  return 0;
}

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

# In[4]:


K,S = map(int, input().split())


# In[6]:


ans = 0
for x in range(K+1):
    diff1 = S-x
    if diff1 >= 0:
        for y in range(K+1):
            z = diff1-y
            if z >= 0 and z <= K:
                ans += 1
print(ans)


# In[ ]:






Measured memory_bytes: 67088
#include <iostream>
#include <vector>
#include <utility>

using namespace std;

typedef pair<int, int> P;

int dist[100001];
vector<P> edge[100001];

bool dfs(int n, int d){
    dist[n] = d;
    for(int i = 0; i < edge[n].size(); i++){
        if(dist[edge[n][i].first] != INT32_MIN && dist[edge[n][i].first] != dist[n] + edge[n][i].second) return false;
        if(dist[edge[n][i].first] == INT32_MIN){
            if(dfs(edge[n][i].first, dist[n] + edge[n][i].second) == false) return false;
        }
    }
    return true;
}

int main(){
    int N, M;
    cin >> N >> M;
    for(int i = 1; i <= N; i++){
        dist[i] = INT32_MIN;
    }
    for(int i = 0; i < M; i++){
        int L, R, D;
        cin >> L >> R >> D;
        edge[L].push_back(P(R, D));
        edge[R].push_back(P(L, -D));
    }
    for(int i = 1; i <= N; i++){
        if(dist[i] == INT32_MIN){
            if(dfs(i, 0) == false){
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
}

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

const int N=1e5+20;

int x,y,a,b,c,va[N],vb[N],vc[N];
priority_queue <int> pq;
long long ans;

int main()
{
	scanf("%d%d%d%d%d",&x,&y,&a,&b,&c);
	for(int i=0;i<a;i++) scanf("%d",&va[i]);
	for(int i=0;i<b;i++) scanf("%d",&vb[i]);
	for(int i=0;i<c;i++) scanf("%d",&vc[i]);

	sort(va,va+a);
	sort(vb,vb+b);
	for(int i=a-x;i<a;i++) pq.push(va[i]);
	for(int i=b-y;i<b;i++) pq.push(vb[i]);
	for(int i=0;i<c;i++) pq.push(vc[i]);

	int r=x+y;
	while(r--) ans+=pq.top(),pq.pop();
	printf("%lld",ans);
}

Measured memory_bytes: 6492
#include<bits/stdc++.h>
#include<boost/variant.hpp>
using namespace std;
typedef long long ll;
typedef vector<boost::variant<bool, ll, int, string, double, char*, const char*>> anys;
template<typename T> inline void pr(const vector<T> &xs){
	for(int i=0; i<xs.size()-1; i++) cout<<xs[i]<<" ";
	(xs.empty()?cout:(cout<<xs[xs.size()-1]))<<endl;
}
#ifdef DEBUG
#define debug(...) pr(anys{__VA_ARGS__})
#define debugv(x) pr((x))
#else
#define debug(...)
#define debugv(x)
#endif

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

	vector<int> ans(N+1);
	for(int i=0; i<N-1; i++) ans[A[i]]++;

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

	return 0;
}


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

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

  vector<ll> h(n+1);

  rep(i, n) cin >> h.at(i);

  h.at(n) = 10000000000;

  int ans = 0;
  int now = 0;

  for(int i = 0; i<n ; i++){
    if(h.at(i) >= h.at(i+1)){
      now++;
    }
    else
    {
      ans = max(now, ans);
      now = 0;
    }
  }

  cout << ans;
}


Measured memory_bytes: 4000
#include <iostream>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <iomanip> // cout<<setprecision(n)
#include <functional> // std::function<void(long long)>
using namespace std;
#define All(v) (v).begin(),(v).end()
const long long mod = 1000000007;
const long long inf = mod*mod;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
long long gcd(long long x, long long y) {
    if (y == 0)return x;
    else return gcd(y, x % y);
}
signed main(){
    vector<int> b(10,0);
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        if(a>=3200){
            b[8]++;
        }
        else{
            b[a/400]=1;
        }
    }
    int c=0;
    for(int i=0;i<8;i++){
        c+=b[i];
    }
    if(b[8]){
        cout<<max(c,1)<<' '<<c+b[8]<<endl;
    }
    else{
        cout<<c<<' '<<c<<endl;
    }
}

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

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rept(i,n) for(int (i)=0;(i)<=(int)(n);(i)++)
#define reps(i,s,n) for(int (i)=(s);(i)<(int)(n);(i)++)
#define repst(i,s,n) for(int (i)=(s);(i)<=(int)(n);(i)++)
#define repr(i,n) for(int (i)=(n);(i)>=0;(i)--)
#define each(itr,v) for(auto (itr):(v))
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define mp(x,y) make_pair((x),(y))
#define fi first
#define se second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define ln "\n"
#define show(x) cout << #x << " = " << x ln
#define dbg(x) cout<<#x"="<<x ln

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

const int inf = (int)1e9;
const ll linf = (ll)1e18;
const int mod = (int)(1e9+7);
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

struct oreno_initializer {
	oreno_initializer() {
		cin.tie(0);
		ios::sync_with_stdio(0);
	}
} oreno_initializer;

// ━━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…
// .｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋
// ・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・

int n;

int main() {
	cin >> n;
	ll a[n];
	rep(i,n) cin >> a[i];
	
	// 一番絶対値がでかい要素を全要素に一回足して符号をそろえる(n回)
	// その後は累積和とっていくだけ(n-1回)
	int id = 0;
	reps(i,1,n) if (abs(a[id])<abs(a[i])) id = i;
	
	cout << n*2-1 << ln;
	rep(i,n) cout << id+1 << " " << i+1 << ln;
	if (a[id]<0) for (int i = n; i > 1; --i) cout << i << " " << i-1 << ln;
	else reps(i,1,n) cout << i << " " << i+1 << ln;
}

Measured memory_bytes: 256
#include <iostream>

int main()
{
    int array[120] = {};

    int n;

    std::cin >> n;

    for (int i = 0; i < n; i++) {
        int b;
        int f;
        int r;
        int v;

        std::cin >> b;
        std::cin >> f;
        std::cin >> r;
        std::cin >> v;

        array[(b - 1) * 30 + (f - 1) * 10 + r - 1] += v;
    }


    for(int i = 0; i < 120; i++) {
        std::cout << " " << array[i];
        if (i % 10 == 9) {
            std::cout << std::endl;
        }

        if (i % 30 == 29 && i < 100) {
            std::cout << "####################" << std::endl;
        }



    }

    return 0;

}

Measured memory_bytes: 1160
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
const int MAXN=1e5+10;
int a[MAXN];
int m,n,l,p,k,ans,tot;
int inline read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main()
{
	n=read();
	if (n<1200)
	{
		printf("ABC");
		return 0;
	 } 
	 
	if (n<2800)
	{
		printf("ARC");
		return 0;
	}
	
	printf("AGC");


	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <cmath>

#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void)
{

    int n, k, tmp, res;
    int d[1000];
    int a[1000] = {0};
    
    
    res = 0;
    
    cin >> n >> k;
    for(int i = 0; i < n; i++)
    {
        cin >> d[i];
        for(int j = 0; j < d[i]; j++)
        {
            cin >> tmp;
            a[tmp - 1]++;
        }
    }
    
    for(int i = 0; i < n; i++)
    {
        if(a[i] == 0)
        {
            res++;
        }
    }
    
    cout << res;
    
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
    set<ll> st;
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    ll n;
    cin >> n;
    vector<ll> x(n), y(n), h(n);
    ll height = 0;
    for (ll i = 0; i < n; i++)
    {
        cin >> x[i] >> y[i] >> h[i];
        if (h[i] != 0)
        {
            height = i;
            st.insert(i);
        }
    }
    if(st.size() == 1){
        cout << x[height] << " " << y[height] << " " <<h[height] << endl;
        return 0; 
    }
    for (ll Cx = 0; Cx <= 100; Cx++)
    {
        for (ll Cy = 0; Cy <= 100; Cy++)
        {
            ll tmp = h[height] + abs(x[height] - Cx) + abs(y[height] - Cy);
            bool highest = true;
            for (auto i : st)
            {
                if (tmp != h[i] + abs(x[i] - Cx) + abs(y[i] - Cy))
                {
                    highest = false;
                    break;
                }
            }
            if (highest)
            {
                cout << Cx << " " << Cy << " " << tmp << endl;
                return 0;
            }
        }
    }
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) list.add(sc.nextInt());

        int min = list.stream().min(Comparator.naturalOrder()).get();
        int max = list.stream().max(Comparator.naturalOrder()).get();
        System.out.println(max-min);
    }
}

Measured memory_bytes: 36200
//
//  main.cpp
//  D
//
//  Created by 曾憲揚 on 2020/8/19.
//  Copyright © 2020 曾憲揚. All rights reserved.
//

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
typedef long long ll;


int main(int argc, const char * argv[]) {
    ll n, k; cin>>n>>k;
    ll ans = 0;
    for(ll i=k; i<=n+1; i++){
        ll s= (i-1)*i/2; ll t=(n+n-i+1)*i/2;
        ans += (t-s+1);
        ans%=MOD;
    }
    cout<<ans<<endl;
    return 0;
}


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

int main()
{
	char s[3];
	for(int i=1;i<=3;i++)
	  cin>>s[i];
	
	if(s[1]==s[2]&&s[1]==s[3])
	{
		cout<<"No";
		return 0;
	}
	
    cout<<"Yes";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cstdlib>  
#include <algorithm>
#include <string>

using namespace std;
 
int main() {
   　string a,b;cin>>a>>b;
     string c = a+b;
     int n = atoi(c.c_str());
     for(int i = 0;i<=1000;i++){
       if(i*i == n){
         cout<<"Yes";
         return 0;
       }
     }
     cout<<"No";
     return 0;
}

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

int main()
{
    int x,y;
    cin >> x >> y;
    int tmp;

    while(x!=0 ||y!=0)
    {
        if(x>y) 
        {
            tmp = x;
            x = y;
            y = tmp;
        }
        cout << x << " " << y << endl;
        cin >> x >> y;
    }
    return 0;
}


Measured memory_bytes: 2988
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

int N;
int A[305][305];
int B[305][305];


int main(){
  cin >> N;
  rep(i,N){
    rep(j,N){
      cin >> A[i][j];
      B[i][j] = A[i][j];
    }
  }
  
  rep(k,N) rep(i,N) rep(j,N) B[i][j] = min(B[i][j], B[i][k]+B[k][j]);


  rep(i,N){
    REP(j,i+1,N){
      if(A[i][j] != B[i][j]){
        cout << "-1" << endl;
        return 0;
      }
    }
  }

  rep(i,N){
    rep(j,N){
      REP(k,i+1,N){
        if(i==j || j==k) continue;
        if(A[i][k] == A[i][j] + A[j][k]){
          //cout << i << " " << j << " " << k << " " << A[i][k] << endl;
          B[i][k] = 0;
        }
      }
    }
  }

  ll sum = 0;
  rep(i,N){
    REP(j,i+1,N){
      sum += B[i][j];
    }
  }
  
  cout << sum << endl;
  
  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
using namespace std;
int main(void){
   string s;
   cin >> s;
   for(int i = 1;i < s.size();i++){
         if(s[i] != '9'){
               cout << s[0] - '0' - 1 + 9 * (s.size() - 1) << endl;
               return 0;
         }
   }
   cout << s[0] - '0' + 9 * (s.size() - 1) << endl;
   return 0;
}


Measured memory_bytes: 256
// Remeber Choose Compiler: GCC9
#include <bits/stdc++.h>

using namespace std;

// Debug Output Utility
#ifdef LOCAL
#define dbg(args...)             \
    do {                         \
        cout << #args << " -> "; \
        err(args);               \
    } while (0)
void err() { std::cout << std::endl; }
template <typename T, typename... Args>
void err(T a, Args... args) {
    std::cout << a << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &... args) {
    for (auto &v : arg)
        std::cout << v << ' ';
    err(args...);
}
#else
#define dbg(...)
#endif

// Macro Definitions:
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

// Type Alias:
using int64 = long long;
using PII   = pair<int, int>;

// Global Const Variable
const int64 INF = 0x3f3f3f3f3f3f3f3f;
const int MOD   = 1000000007;
const int MAXN  = 200005;

int64 a[MAXN], b[MAXN];
int64 n, m, k;

int64 f(int64 mid) { // 在 a 中选 mid 个
    return mid + (upper_bound(b, b + m, k - (mid > 0 ? a[mid - 1] : 0)) - b);
}

void run() {
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i < n; i++)
        a[i] += a[i - 1];
    for (int i = 0; i < m; i++) {
        cin >> b[i];
    }
    for (int i = 1; i < m; i++)
        b[i] += b[i - 1];
    int64 beg = 0, end = upper_bound(a, a + n, k) - a;
    int64 ans = 0;
    for (int64 i = beg; i <= end; i++) {
        // dbg(i, f(i) - i);
        ans = max(ans, f(i));
    }
    cout << ans << endl;
}

// Debug Input Redirection
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    run();
}


Measured memory_bytes: 6724
#include<bits/stdc++.h>
using namespace std;
int main(){
  int A,B;
  cin >> A >> B;
  if(A<=5){
    cout << 0 << endl;
  }else if(A>=13){
    cout << B << endl;
  }else{
    cout << B/2 << endl;
  }
}


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

int main(){
  int n,m,i;
  cin >> n >> m;
  vector<int> h(n),a(m),b(m),g(n,1);
  for(i=0;i<n;i++){
    cin >> h.at(i);
  }
  for(i=0;i<m;i++){
    cin >> a.at(i) >> b.at(i);
    if(h.at(a.at(i)-1)>=h.at(b.at(i)-1)){
      g.at(b.at(i)-1)=0;
    }
    if(h.at(a.at(i)-1)<=h.at(b.at(i)-1)){
      g.at(a.at(i)-1)=0;
    }
  }
  
  int s=0;
  for(i=0;i<n;i++){
    s+=g.at(i);
  }
  cout << s << endl;
}

Measured memory_bytes: 4800
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MM 1000000000
#define MOD MM+7
#define MAX 301000
#define MAP 110
#define initial_value -1
#define Pair pair<int,int>
#define chmax(a,b) (a<b ? a=b:0)
#define chmin(a,b) (a>b ? a=b:0)
ll INF = 1e18;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
int depth[100100];
int par[100100];

struct UnionFind {
    vector<int> par;
    UnionFind(int n) : par(n,-1) {}
    void init(int n) { par.assign(n,-1);}
    int root(int x){
        if(par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    bool same(int x, int y){
        return root(x) == root(y);
    }
    bool merge(int x, int y){
        x = root(x); y = root(y);
        if(x == y) return false;
        if(par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    int size(int x){
        return -par[root(x)];
    }
};

int main(){
    ll N,M; cin >> N >> M;
    //初期化
    vector<ll> A(M),B(M);
    for(int i = 0; i < M; i++){
        cin >> A[i] >> B[i];
        A[i]--; B[i]--;
    }
    UnionFind uf(N);
    ll cur = N*(N-1)/2;
    vector<ll> res;
    for(int i = 0; i < M; i++){
        res.push_back(cur);
        //逆順から連結していく
        int a = A[M-i-1], b = B[M-i-1];
        if(uf.same(a,b)) continue;
        //else 
        ll sa = uf.size(a), sb = uf.size(b);
        //
        cur -= sa*sb;
        //結合
        uf.merge(a,b);
    }
    //元の順番で出力
    reverse(res.begin(),res.end());
    for(int i = 0; i < res.size(); i++) cout << res[i] << endl;
}


Measured memory_bytes: 4212
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define rep(i, n) repd(i, 0, n)

using namespace std;

namespace mp = boost::multiprecision;

using ll = long long;
using Bint = mp::cpp_int;
ll mod = pow(10, 9) + 7;

int main() {
    // source
    ll n;
    cin >> n;
    ll n_temp;
    ll ans = 0;
    vector<ll> memo;

    if (n % 2 == 1) {
        ans = 0;
    } else {
        n /= 2;
        while (n > 0) {
            ans += n / 5;
            n /= 5;
        }
    }

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



Measured memory_bytes: 256
#include<stdio.h>
#define pi 3.141592653589
int main()
{
	double r,ensyu,menseki;
	scanf("%lf",&r);
	ensyu=2.0*pi*r;
	menseki=pi*r*r;
	printf("%f %f\n",menseki,ensyu);
return 0;
}


Measured memory_bytes: 2000
#include <bits/stdc++.h>
using namespace std;
int n, L, R, p = 1000000007;
long long a[100020], A, B;
int f[100020];
int s[100020];
int main() {
	scanf("%d%lld%lld", &n, &A, &B);
	if (A > B) {
		swap(A, B);
	}
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
	}
	for (int i = 3; i <= n; i++) {
		if (a[i] - a[i - 2] < A) {
			printf("0\n");
			return 0;
		}
	}
	a[0] = a[1] - B;
	s[1] = f[0] = 1;
	for (int i = 1; i <= n; i++) {
		while (a[i] - a[R] >= B) {
			R++;
		}
		f[i] = (s[R] - s[L] + p) % p;
		s[i + 1] = (s[i] + f[i]) % p;
		if (i > 0 && a[i] - a[i - 1] < A) {
			L = i - 1;
			R = max(R, L);
		}
	}
	printf("%d\n", (s[n + 1] - s[L] + p) % p);
	return 0;
}

Measured memory_bytes: 1792
def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a

def lcm(x, y):
    return (x * y) // gcd(x, y)


A, B, C, D = map(int, input().split())
ans = set()
if A%C == 0:
    c = (B//C) - (A//C) + 1
else:
    c = (B//C) - (A//C)

if A%D == 0:
    d = (B//D) - (A//D) + 1
else:
    d = (B//D) - (A//D)

CD = lcm(C, D)

if A%CD == 0:
    cd = (B//CD) - (A//CD) + 1
else:
    cd = (B//CD) - (A//CD)

print(B - A + 1 - (c+d-cd))

Measured memory_bytes: 3064