akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    int N;
    std::cin >> N;
    std::vector<int> P(N), Q(N);
    for(int i=0; i<N; i++){
        scanf(" %d", &P[i]); P[i]--;
        Q[P[i]] = i;
    }

    std::vector<int> count(N);
    count[0] = 1;
    for(int i=1; i<N; i++){
        if(Q[i-1] < Q[i]) count[i] = count[i-1] + 1;
        else count[i] = 1;
    }
    // for(int& q: Q) printf("Q: %d\n", q);

    std::cout << N - *max_element(count.begin(), count.end()) << std::endl;
}

Measured memory_bytes: 2688
N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(3 ** N):
    mul = 1
    for j in range(N):
        mod = i // (3 ** j) % 3
        if mod == 0:
            mul *= A[j] - 1
        elif mod == 1:
            mul *= A[j]
        else:
            mul *= A[j] + 1
    if mul % 2 == 0:
        ans += 1
print(ans)


Measured memory_bytes: 3060
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
int main(){
  ll a,b,c,k,ans=0;cin>>a>>b>>c>>k;
  if(a<=k){
    k-=a;
    ans+=a;
  }else{
    ans+=k;
    k=0;
  }
  if(b<=k){
    k-=b;
  }else{
    k=0;
  }
  if(c<=k){
    k-=c;
    ans-=c;
  }else{
    ans-=k;
    k=0;
  }
  cout << ans<< endl;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
typedef long long  ll;
#define press_F_to_pay_respect ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define forn for(int i=0;i<n;i++) 
#define form for(int j=0;j<n;j++) 
#define fora(i,a,b) for(int i = a; i < (b); i++)
#define pb push_back 
#define pob pop_back()
#define mp make_pair 
#define sc second 
#define f first 
#define kek cout<<endl; 
#define all(v) ((v).begin()), ((v).end()) 
#define pob pop_back() 
#define halt {cout<<"No"; return 0;}
const ll MOD = 1e9 + 7;
const int N = 200005;
const int INF = 1e8;
const ll MOD1=998244353;
using namespace std;

int main()
{
#if defined(_DEBUG)
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
 press_F_to_pay_respect;
 // cout << fixed << setprecision(12) << ans;
int n;
cin>>n;
ll dp[n+1];
dp[0]=2;
dp[1]=1;
for(int i=2;i<=n;i++) dp[i]=dp[i-1]+dp[i-2];
cout<<dp[n];
return 0;
 

}

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

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<int> l(n);
    for (int i = 0; i < n; ++i) {
        if (a[i] == 0 && (i == 0 || a[i - 1] != 0)) {
            l[i]++;
        } else if (i != 0 && a[i - 1] == 0 && a[i] != 0) {
            l[i]--;
        }
    }
    for (int i = 1; i < n; ++i) {
        l[i] += l[i - 1];
    }
    for (int i = n - 2; i >= 0; --i) {
        if (l[i] != 0) l[i] += l[i + 1];
    }
    /*for (auto it : l) {
        cout << it << " ";
    }
    cout << "\n";*/
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        int mask = 0, sm = 0, j = 0;
        while (i + j < n && (mask ^ a[i + j]) == sm + a[i + j]) {
            if (l[i + j] == 0) ans++;
            else ans += l[i + j];
            //ans++;
            sm += a[i + j];
            mask ^= a[i + j];
            if (l[i + j] == 0) j++;
            else j += l[i + j];
            //j++;
        }
        //cout << ans << "\n";
    }
    cout << ans << "\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}


Measured memory_bytes: 3328
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;
int a[1005];
int main()
{
   int n,i,j;

   int s1=0,s2=0;
   int ans=1000000;
   scanf("%d",&n);
    for(i=1;i<=n;i++){scanf("%d",&a[i]);s2+=a[i];}
   for(i=1;i<=n;i++)
   {
       s1+=a[i];
       s2-=a[i];

       if(ans>abs(s1-s2))ans=abs(s1-s2);
   }
   printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    
    int X, happy=0;
    cin >> X;
    if(X>=500){
        happy+=1000*(X/500);
        X=X-500*(X/500);
    }
    if(X>=5){
        happy+=5*(X/5);
    }
    cout << happy << endl;
    
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n)  for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define deb(x) cerr << #x <<": " << x << '\n';
#define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
typedef long double ld;
typedef long long ll;

int main(){
    ios;
    int a, b; cin >> a >> b;
    int ans = min(a,b);
    rep(i,max(a,b)){
        cout << ans;
    }
}


Measured memory_bytes: 256
import java.util.*;

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

    int n = sc.nextInt();
    String s[] = new String[n];
    for (int i = 0; i < n; i++) {
      s[i] = sc.next();
      if (i > 0) {
        if (s[i-1].charAt(s[i-1].length()-1) != s[i].charAt(0)) {
          System.out.println("No");
          return;
        }
        for (int j = 0; j < i; j++) {
          if (s[j].equals(s[i])) {
            System.out.println("No");
            return;
          }
        }
      }
    }
    System.out.println("Yes");
  }
}


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

#ifdef _DEBUG
#define ASSERT(x) assert(x)
#define DLOG(x) cout << #x " " << x << endl;
#else
#define ASSERT(x)
#define DLOG(x)
#endif

using namespace std;

struct Node {
  int left;
  int right;
};

void preorder(vector<int>& result, const vector<Node>& nodes, int current) {
  if (current == -1) {
    return;
  }
  ASSERT(current < nodes.size());
  auto& node = nodes[current];
  result.push_back(current);
  preorder(result, nodes, node.left);
  preorder(result, nodes, node.right);
}

void inorder(vector<int>& result, const vector<Node>& nodes, int current) {
  if (current == -1) {
    return;
  }
  ASSERT(current < nodes.size());
  auto& node = nodes[current];
  inorder(result, nodes, node.left);
  result.push_back(current);
  inorder(result, nodes, node.right);
}

void postorder(vector<int>& result, const vector<Node>& nodes, int current) {
  if (current == -1) {
    return;
  }
  ASSERT(current < nodes.size());
  auto& node = nodes[current];
  postorder(result, nodes, node.left);
  postorder(result, nodes, node.right);
  result.push_back(current);
}

void printResult(const vector<int>& result) {
  for (auto&& id : result) {
    cout << " " << id;
  }
  cout << endl;
}

int main() {
  int num;
  cin >> num;
  vector<Node> nodes(num, Node{});
  set<int> rootCandidates;
  for (int i = 0; i < num; ++i) {
    rootCandidates.insert(i);
  }
  for (int i = 0; i < num; ++i) {
    int id, left, right;
    cin >> id >> left >> right;
    ASSERT(id < nodes.size());
    nodes[id].left = left;
    nodes[id].right = right;
    rootCandidates.erase(left);
    rootCandidates.erase(right);
  }
  ASSERT(rootCandidates.size() == 1);
  int root = *rootCandidates.begin();
  vector<int> result;
  preorder(result, nodes, root);
  cout << "Preorder" << endl;
  printResult(result);
  result.clear();
  inorder(result, nodes, root);
  cout << "Inorder" << endl;
  printResult(result);
  result.clear();
  postorder(result, nodes, root);
  cout << "Postorder" << endl;
  printResult(result);
}



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

int main() {
  string s;
  int n;
  cin >> n >> s;
  if (n % 2 == 1) printf("No\n");
  else {
    int i = 0;
    while ((i < s.size()/2) && (s[i] == s[i+s.size()/2])) i++;
    if (i == s.size()/2) printf("Yes\n");
    else printf("No\n");
  }
  return 0;}


Measured memory_bytes: 256
N,K=gets.chomp.split.map(&:to_i)
array=(1..N).to_a
K.times{
  a=gets.to_i
  gets.split.map(&:to_i).each do |n|
    array=array.select{|k| k!=n}
    if array.size==0
      break
    end
  end
}
puts array.size

Measured memory_bytes: 14404
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args)  {
        StringBuilder sb = new StringBuilder();
        try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int n = Integer.parseInt(br.readLine());
            String[] split = br.readLine().split("\\s+");
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < split.length; j++) {
                    sb.append(split[j].charAt(i));
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
        System.out.println(sb.toString());
    }
}

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

using namespace std;

typedef long long ll;

inline int gi()
{
	int f = 1, x = 0; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = getchar();
	return f * x;
}

int n, k, s;

int main()
{
	n = gi(), k = gi(), s = gi();
	for (int i = 1; i <= k; i+=1) cout << s << ' ';
	if (s != 1e9)
	{
		for (int i = k + 1; i <= n; i+=1) cout << s + 1 << ' ';
		puts("");
		return 0;
	}
	else
	{
		for (int i = k + 1; i <= n; i+=1) cout << 999999999 << ' ';
		puts("");
		return 0;
	}
	return 0;
}


Measured memory_bytes: 1280
//Optional FAST

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,fma,abm,mmx,avx,avx2,tune=native")

//Required Libraries

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

//Required namespaces

using namespace std;
using namespace __gnu_pbds;

//Required defines

#define endl '\n'

#define READ(X) cin>>X;
#define READV(X) long long X; cin>>X;
#define READAR(A,N) long long A[N]; for(long long i=0;i<N;i++) {cin>>A[i];}
#define rz(A,N) A.resize(N);
#define sz(X) (long long)(X.size())
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define trav(x,A) for(auto &x:A)
#define FORI(a,b,c) for(long long a=b;a<c;a++)
#define FORD(a,b,c) for(long long a=b;a>c;a--)

//Required typedefs

typedef tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<long long,null_type,greater<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set1;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef vector<int> veci;
typedef vector<long long> vecl;

//Required Constants

const long long inf=(long long)1e18;
const long long MOD=(long long)(1e9+7);
const long long INIT=(long long)(1e6+1);

//Required Functions

ll power(ll x,ll y) 
{ 
	if (y == 0) 
		return 1; 
	ll p = power(x, y/2) % MOD; 
	p = (p * p) % MOD; 
  
	return (y%2 == 0)? p : (x * p) % MOD; 
}
ll modInverse(ll a) 
{ 
   return power(a,MOD-2); 
   
}

//Work

int main()
{
	#ifndef ONLINE_JUDGE
	if (fopen("INPUT.txt", "r"))
	{
		freopen ("INPUT.txt" , "r" , stdin);
		//freopen ("OUTPUT.txt" , "w" , stdout);
	}
	#endif
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	clock_t clk;
	clk = clock();
//-----------------------------------------------------------------------------------------------------------//

	READV(N);
	READV(M);
	READAR(A,N);
	ll tot=0;
	FORI(i,0,N)
	{
		tot+=A[i];

	}
	tot=(tot+4*M-1)/(4*M);
	FORI(i,0,N)
	{
		if(A[i]>=tot)
		{
			M--;
		}
	}
	if(M<=0)
	{
		cout<<"Yes"<<endl;
	}
	else
	{
		cout<<"No"<<endl;
	}
	

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


	clk = clock() - clk;
	cerr << fixed << setprecision(6) << "Time: " << ((double)clk)/CLOCKS_PER_SEC << endl;

	return 0;
}

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

int main(){

    int D, N;
    cin >> D >> N;
    vector<int> A(N);
    int ans = 0;

    if (N != 100){    
        if (D == 0) ans = 1*N;
        else if (D == 1) ans = 100*N;
        else ans = 10000*N;
    }
    else {
        if (D == 0) ans = 101;
        else if (D == 1) ans = 100*(99+2);
        else ans = 10000*(99+2);
    } 

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

Measured memory_bytes: 3620
#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
using i64 = long long;

int main()
{
  i64 n;
  cin >> n;
  vector<i64> a(n);
  for (i64 i = 0; i < n; i++)
    cin >> a[i];
  i64 ans = 0;
  for (i64 i = 0; i < n; i++)
  {
    ans += a[i] / 2;
    a[i] %= 2;
    if (i < n - 1 && 0 < a[i] && 0 < a[i + 1])
    {
      ans++;
      a[i]--;
      a[i + 1]--;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
  
using namespace std;
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
#define REP(i,n) for(ll i=0;i<n;++i)
#define REPR(i,n) for(ll i=1;i<n;++i)
#define FOR(i,a,b) for(ll i=a;i<b;++i)
  
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()
  
#define MOD (ll)(1e9+7)
#define ADD(a,b) a=((a)+(b))%MOD
#define FIX(a) ((a)%MOD+MOD)%MOD

#define INF 1000000000

typedef long double Real;
#define EPS 1e-11
#define EQ(x) (-EPS<x && x<EPS)
typedef complex<Real> P;
Real dot(P a,P b){return real(conj(a)*b);}
Real cross(P a,P b){return imag(conj(a)*b);}

int main(){
  int cnt = 0;
  P a,b,c;
  float x,y;
  Real s = 0;
  while(~scanf("%f,%f",&x,&y)){
    if(x==1145141919)break;
    if(cnt==0) a=P(x,y);
    else if(cnt==1) b=P(x,y);
    else{
      c=P(x,y);
      s += abs(cross(b-a,c-a))/2.0;
      b=c;
    }
    ++cnt;
  }
  cout.precision(12);
  cout<<fixed<<s<<endl;
  return 0;
}

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

using namespace std;

#define uint unsigned int
#define llong long long int
#define ullong unsigned long long int
#define rep(i, n) for (int i = 0; i < n; ++i)

const static long long int MOD = 1000000000 + 7;
const static int dy[] = {0, 1, 0, -1};
const static int dx[] = {1, 0, -1, 0};

int main (int argc, char *argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, m, X[100001] = {};
    cin >> n >> m;
    rep(i, m) {
        cin >> X[i];
    }
    if (n >= m) {
        cout << 0 << endl;
        return 0;
    }

    sort(X, X + m);
    priority_queue <llong, vector<llong>, greater<llong> > D;
    llong sum = 0;
    for (int i = 1; i < m; ++i) {
        D.push(abs(X[i] - X[i - 1]));
    }

    for (int i = 0; i < m - n; ++i) {
        sum += D.top();
        D.pop();

    }

    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 1784
sa = [s for s in input()]
sb = [s for s in input()]
sc = [s for s in input()]

next_turn = "a"
flag = True

while flag:
    if next_turn == "a":
        if len(sa) == 0:
            print("A")
            flag = False
        else:
            next_turn = sa.pop(0)
    elif next_turn == "b":
        if len(sb) == 0:
            print("B")
            flag = False
        else:
            next_turn = sb.pop(0)
    elif next_turn == "c":
        if len(sc) == 0:
            print("C")
            flag = False
        else:
            next_turn = sc.pop(0)

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

int main(){
  int n;
  cin >> n;
  string s;
  cin >> s;
  int i=0, j=n-1, ans=0;
  while(1){
    while(i<j and s[i]=='R')
      	++i;
    while(i<j and s[j]=='W')
      	--j;
    if(i==j)
      break;
    swap(s[i],s[j]);
    ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3748
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <cmath>   
#include<cctype>
#include<string>
#include<set>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
#define all(x) (x).begin(),(x).end()
#define rep(i,m,n) for(int i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(int i = m;i >= n;--i)
#define INF INT_MAX/2
using namespace std;
using ll = long long;
using R = double;
const ll inf = 1LL << 50;
const ll MOD = 1e9 + 7;
struct edge { ll from; ll to; ll cost; };

int sum[101010];

int main(){
	int n, q;
	string s;
	cin >> n >> q >> s;

	int pre = 0;
	rep(i, 0, n) {
		if (s[i] == 'A') { 
			pre = 1; 
			continue;
		}
		else if (s[i] == 'C' && pre) { 
			sum[i+1] = 1;
		}
		pre = 0;
	}
	rep(i, 0, 101005) {
		sum[i + 1] += sum[i];
	}

	rep(i, 0, q) {
		int l, r;
		cin >> l >> r;
		cout << sum[r] - sum[l] << endl;
	}
	return 0;
}

Measured memory_bytes: 1408
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def main():
    A = int(input())
    B = int(input())

    if A == B:
        print("EQUAL")
    elif A > B:
        print("GREATER")
    else:
        print("LESS")


if __name__ == '__main__':
    main()


Measured memory_bytes: 3948
#include <iostream>
#include <iterator>
#include <unordered_map>
#include <algorithm>
using namespace std;
 
using ll = long long;
int const a[] { 2, 3, 5 };
int b[3], d;
 
ll f(ll n, unordered_map<ll, ll>& memo) {
    ll& ans = memo[n];
    if (n > 0 && ans == 0) {
        ans = 1e12;
        if (n < ans / d)
            ans = n * d;
        for (int i = 3; i--;) {
            int p = a[i], c = b[i];
            ll k = n / p, r = n % p;
            ans = min({ ans, f(k, memo) + r * d + c, r ? f(k + 1, memo) + (p - r) * d + c : ans });
        }
    }
    return ans;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t;
    for (cin >> t; t--;) {
        ll n;
        cin >> n;
        copy_n(istream_iterator<int>(cin), 3, b);
        cin >> d;
        unordered_map<ll, ll> memo{ {1, d} };
        cout << f(n, memo) << '\n';
    }
    return 0;
}


Measured memory_bytes: 4072
#include<stdio.h>
#include<stdio.h>
int main(){
  char s[10000 + 10];
  int i,n;
  scanf("%d %s",&n,s);
  for(i=0;i<strlen(s);i++){
    if((int)s[i] + n > 90)
      s[i] = (char)((int)'A' + (s[i] + n - 91));
    else
      s[i] = (char)((int)s[i] + n);
  }
  printf("%s",s);
  return 0;
}

Measured memory_bytes: 128
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<queue>
using namespace std;
typedef long long LL;
const int maxn = 100000+5;
const LL mod = 1000000007;
struct Node {
    int l,r,sum,c;
}t[maxn<<2];
struct Seg {
    int l,r;
}s[maxn+(maxn<<1)];
vector<int>g[maxn];
void build(int l,int r,int rt) {
    t[rt].l=l;
    t[rt].r=r;
    t[rt].sum=0;
    t[rt].c=0;
    if (l == r) {
        return ;
    }
    int mid = l + r >> 1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    return ;
}
void pd(int &rt) {
    if (!t[rt].c) {
        return ;
    }
    int len = t[rt].r - t[rt].l + 1;
    t[rt<<1].sum+=t[rt].c*(len-(len>>1));
    t[rt<<1|1].sum+=t[rt].c*(len>>1);
    t[rt<<1].c+=t[rt].c;
    t[rt<<1|1].c+=t[rt].c;
    t[rt].c=0;
    return ;
}
void update(int l,int r,int rt,int val) {
    if (l<=t[rt].l&&t[rt].r<=r) {
        t[rt].sum+=val*(t[rt].r-t[rt].l+1);
        t[rt].c+=val;
        return ;
    }
    pd(rt);
    int mid = t[rt].l + t[rt].r >> 1;
    if (l <= mid) {
        update(l,r,rt<<1,val);
    }
    if (r>mid) {
        update(l,r,rt<<1|1,val);
    }
    t[rt].sum=t[rt<<1].sum+t[rt<<1|1].sum;
    return ;
}
int query(int l,int r,int rt) {
    if (l<=t[rt].l&&t[rt].r<=r) {
        return t[rt].sum;
    }
    pd(rt);
    int mid = t[rt].l + t[rt].r >> 1;
    int res = 0;
    if (l <= mid) {
        res+=query(l,r,rt<<1);
    }
    if (r > mid) {
        res+=query(l,r,rt<<1|1);
    }
    return res;
}
int main() {
    
    int n,m;
    scanf("%d%d",&n,&m);
    build(1,m,1);
    for (int i=1;i<=n;++i) {
        scanf("%d%d",&s[i].l,&s[i].r);
        int len=s[i].r-s[i].l+1;
        g[len].push_back(i);
    }
    for (int i=1;i<=m;++i) {
        int ans=0;
        for (int j=0;j<g[i-1].size();++j) {
            int pos=g[i-1][j];
            update(s[pos].l,s[pos].r,1,1);
        }
        n-=g[i-1].size();
        for (int j=i;j<=m;j+=i) {
            ans+=query(j,j,1);
        }
        printf("%d\n",ans+n);
    }
    return 0;
}

Measured memory_bytes: 14208
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = INT()
sp = [S_LIST() for _ in range(n)]
for i in range(n):
    sp[i][1] = float(1 / (int(sp[i][1]) + 1))
    sp[i].append(i + 1)
sp.sort()
for i in range(n):
    print(sp[i][2])


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

using namespace std;
typedef long long ll;
int NumberOfTriangles(int arr[], int n)
{
	int counter = 0;
 
        sort(arr,arr+n); //sort the array in non-decreasing order
	
	for (int i = 0; i < n-2; ++i)     // fix the first element
	{
		
		int k = i+2;             // fix the third element (this is the largest one among three elements as array is sorted)
 
		for (int j = i+1; j < n; ++j)    //fix the second element
		{
			while (k < n && arr[i] + arr[j] > arr[k])        //checking triangle property
			        ++k;
			counter += (k - j - 1);                          //total number of possible triangles that can be formed
		}
	}
 
	return counter;
}

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

	int n;
	cin>>n;

	int l[n+5];

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

	cout<<NumberOfTriangles(l,n)<<'\n';

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;
typedef vector<string> vss;
struct Solution {
    void solve(std::istream& in, std::ostream& out) {
        ll h, w;
        in >> h >> w;
        vss s(h);
        for (int i = 0; i < h; i++) {
            in >> s[i];
        }
        ll cnt = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cnt += s[i][j] == '#';
            }
        }
        if (cnt == h + w - 1) {
            out << "Possible" << '\n';
        }
        else {
            out << "Impossible" << '\n';
        }
    }
};
void solve(std::istream& in, std::ostream& out) {
    out << std::setprecision(12);
    Solution solution;
    solution.solve(in, out);
}
#include <fstream>
#include <iostream>
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    istream& in = cin;
    ostream& out = cout;
    solve(in, out);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;
using int64    = long long;
using PII      = pair<int, int>;
const int MAXN = 80;
const int INF  = 0x3f3f3f3f;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    int64 a;
    string b;
    cin >> a >> b;
    int64 ans = a*(b[0]-'0')*100+a*(b[2]-'0')*10+a*(b[3]-'0');
    cout << ans/100 << endl;
}


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

const int mod = 998244353;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

const int MAX_N = 200005;
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
} c(MAX_N);

int main() {
  int n, m, k; cin >> n >> m >> k;

  mint col = m;
  mint sum = 0;
  for (int i = n-1; i >= 0; i--) {
    mint now = col * c(n-1,i);
    if (i <= k) sum += now;
    col *= m-1;
  }

  cout << sum << endl;
}


Measured memory_bytes: 6188
#import bisect
#from collections import product
n = int(input())

co_x = set()
co_y = set()
Rec = []
for _ in range(n):
    x1,y1,x2,y2 = map(int, input().split( ))
    co_x = co_x | {x1,x2}
    co_y = co_y | {y1,y2}
    Rec.append([x1,y1,x2,y2])

Rec.sort()

co_x = list(co_x)
co_y = list(co_y)

co_x.sort()
co_y.sort()

r = len(co_x)
l = len(co_y)

#Rec_press = []
"""
for p in Rec:
    ix0 = bisect.bisect_left(co_x,p[0])
    iy0 = bisect.bisect_left(co_x,p[1])
    ix1 = bisect.bisect_left(co_x,p[2])
    iy1 = bisect.bisect_left(co_x,p[3])
    Rec_press.append([ix0,iy0,ix1,iy1])
    
#以上圧縮

"""
#3161838 By JAKENU0X5E参照
mx = {x:i for i,x in enumerate(co_x)}
my = {y:i for i,y in enumerate(co_y)}
h = len(mx)
w = len(my)
#print(mx,my)

s = [[0]*(w+1) for i in range(h+1)]
for p in Rec:
    p1 = mx[p[0]]
    q1 = my[p[1]]
    p2 = mx[p[2]]
    q2 = my[p[3]]
    
    s[p1][q1] += 1
    s[p1][q2] -= 1
    s[p2][q1] -= 1
    s[p2][q2] += 1

"""
この時点でのs[p][q]は被覆開始のフラグ
次のforで直前のs[i][j]に応じてs[i][j+1],s[i+1][j+1]を+1することで
sが被覆されているか否かのフラグになる
"""
    

for i in range(h):
    for j in range(w):
        s[i][j+1] += s[i][j]
for j in range(w):
    for i in range(h):
        s[i+1][j] += s[i][j]

ans = 0

for i in range(h):
    for j in range(w):
        if s[i][j]:
            #print(co_x[i],co_y[j],co_x[i+1],co_y[j+1],(co_x[i+1]-co_x[i])*(co_y[j+1]-co_y[j]))
            ans += (co_x[i+1]-co_x[i])*(co_y[j+1]-co_y[j])

print(ans)


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

#define rep(i,N) for(int i=0;i<N;i++)
#define rep2(i,N) for(int i=1;i<=N;i++)
using namespace std;
long long  INF=1e18;
long long mod=1e9+7;

//status unsolved
int main(){

    long long n,k;
    cin>>n>>k;
    
    long long a[n];
    int pos=-1;
    rep(i,n){
        cin>>a[i];
        if(a[i]==1){
            pos=i;
        }
    }

    //int left=ceil((double)abs(pos-0)/(k-1));
    //int right=ceil((double)abs((n-1)-pos)/(k-1));
    //cout<<right<<endl;
    //cout<<left<<endl;

    cout<<ceil((double)(n-1)/(k-1))<<endl;
    return 0;

}
/*


*/


Measured memory_bytes: 1024
#include <stdio.h>

int main(void)
{
	int i, j;
	int n, flg = 0;
	scanf("%d", &n);

	for (i = 0; i <= n / 4; i++)
	{
		for (j = 0; j <= n / 7; j++)
		{
			if ((i * 4 + j * 7) == n)
			{
				flg = 1;
				printf("Yes");
				break;
			}
		}
		if (flg == 1)
		{
			break;
		}
	}

	if (flg == 0)
	{
		printf("No");
	}

	return 0;
}

Measured memory_bytes: 128
#ifndef ONLINE_JUDGE
  #include "Debug.h"
#else
  #define debug(...) 42
#endif
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define f(i,x,n) for(int i=x;i<n;i++) 
#define all(c) c.begin(),c.end()
const int MOD = 1e9 + 7, N = 5e5 + 10;
const int LINF = LLONG_MAX;

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int h,w,m;
    cin >> h >> w >> m;
    map<pair<int,int>,int>maps;
    f(i,1,m+1){
        int x,y;
        cin >> x >> y;
        maps[{x,y}] = 1;
    }
    vector<int>row(h+1,0),col(w+1,0);
    for(auto s : maps){
        row[s.first.first]++;
        col[s.first.second]++;
    }
    vector<int>x,y;
    int ans = 0;
    for(auto s : maps){
        x.push_back(s.first.first);
        y.push_back(s.first.second);
    }
    int a = x.size();
    int b = y.size();
    int ind_x,ind_y;
    int ma_x = 0,ma_y = 0;
    f(i,1,h+1){
        if(row[i] > ma_x){
            ma_x = row[i];
            ind_x = i;
        }
    }
    f(i,1,w+1){
        ans = max(ans,col[i] + ma_x - maps[{ind_x,i}]);
    }
    f(i,1,w+1){
        if(col[i] > ma_y){
            ma_y = col[i];
            ind_y = i;
        }
    }
    f(i,1,h+1){
        ans = max(ans,row[i] + ma_y - maps[{i,ind_y}]);
    }
    cout << ans << "\n";

    return 0;
}
 

Measured memory_bytes: 68808
#include <bits/stdc++.h>
using namespace std;typedef long long ll;typedef vector<ll> vll;
int main(){
  ll n, ans = 0;
  cin >> n;
  vll a(n);
  for (ll i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (ll i = 0; i < n-2; i++) {
    if ((a[i] < a[i+1] && a[i+1] < a[i+2]) ||
       (a[i+2] < a[i+1] && a[i+1] < a[i])) {
      ans++;
    }
  }
  
  cout << ans << endl;
}

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

namespace ALDS1_9_A {
    class Program {
        static void Main(string[] args) {
            int H = int.Parse(Console.ReadLine());
            Dictionary<int, int> keys = Console.ReadLine().Split(' ')
                .Select((key, index) => new { index, key })
                .ToDictionary(n => n.index + 1, n => int.Parse(n.key));

            StringBuilder sb = new StringBuilder();
            for(int i = 1; i <= H; i++) {
                int p = GetParentId(i);
                int l = GetLeftId(i);
                int r = GetRightId(i);

                sb.Append("node " + i);
                sb.Append(": key = " + keys[i] + ", ");
                if (p > 0)
                    sb.Append("parent key = " + keys[p] + ", ");
                if (l <= H)
                    sb.Append("left key = " + keys[l] + ", ");
                if (r <= H)
                    sb.Append("right key = " + keys[r] + ", ");
                sb.AppendLine();
            }
            Console.Write(sb);
        }

        static int GetParentId(int id) {
            return id / 2;
        }

        static int GetLeftId(int id) {
            return 2 * id;
        }

        static int GetRightId(int id) {
            return 2 * id + 1;
        }
    }
}

Measured memory_bytes: 10232
import java.util.Scanner;

public class Main {
    public static Scanner sc;
    public static void main(String[] args) throws Exception {
        sc = new Scanner(System.in);
        sc.nextInt();
        while (sc.hasNext()) {
            int u = 0;
            int d = 0;
            int n = sc.nextInt();
            
            int a = sc.nextInt();
            for (int i = 0; i < n-1; i++) {
                int b = sc.nextInt();
                int diff = b - a;
                if (diff > u) {
                    u = diff;
                } else if (diff < d) {
                    d = diff;
                }
                a = b;
            }
            
            System.out.println(u + " " + d*-1);
        }
    }
}

Measured memory_bytes: 35464
#include <iostream>
#include <math.h>
#include <algorithm>
#include <functional> 
#include <string>
#include <vector>

#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <utility>

using namespace std;

typedef long long LL;

#define dump(c) { for (auto it = c.begin(); it != c.end(); ++it) if (it == c.begin()) cout << *it; else cout << ' ' << *it; cout << endl; } 
#define rep(i,n) for (int i = 0; i < (n); ++i)

const int MOD = 1000000007;


inline int nodeIndex(int i, int m)
{
    return i * 3 + m;
}


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

    vector<vector<int>> n(3*N);
    rep(i, M) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        rep(m, 3) {
            n[nodeIndex(u, m)].push_back(nodeIndex(v, (m+1)%3));
        }
    }

    int S, T;
    cin >> S >> T;
    --S; 
    --T;

    //! find the shortest path from n[nodeIndex(S,0)] to n[nodeIndex(T,0)]
    vector<int> len(3*N, -1); //! length from (S,0)
    queue<int> q; //! nodes to be visited

    //! start from (S,0)
    len[nodeIndex(S, 0)] = 0;
    q.push(nodeIndex(S,0));
    int ans = -1;
    int goal = nodeIndex(T, 0);

    while (!q.empty() && ans < 0) {
        int curr = q.front(); q.pop();
        for (int next: n[curr]) {
            if (len[next] < 0) { //! if not visited yet
                len[next] = len[curr] + 1;
                if (next == goal) {
                    ans = len[next] / 3;
                    break;
                } else {
                    q.push(next);
                }
            }
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 17792
#[allow(unused_macros)]
macro_rules! parse_line {
    ( $t:ty ) => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            iter.next().unwrap().parse::<$t>().unwrap()
        }
    );

    ( $( $t:ty), +) => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            ( $(iter.next().unwrap().parse::<$t>().unwrap()),* )
        }
    );
}

#[allow(unused_macros)]
macro_rules! read_line {
    () => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            line.pop();
            line
        }
    )
}

#[allow(unused_macros)]
macro_rules! parse_vec {
    ( $t:ty ) => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            let iter = line.split_whitespace();
            iter.map(|v| v.parse::<$t>().unwrap()).collect::<Vec<_>>()
        }
    )
}

fn solve(h: i64, abs: Vec<(i64, i64)>) -> i64 {
    let max_a = abs.iter().fold(0, |max, x| if max < x.0 {x.0} else {max});

    let mut bs = abs.iter().filter(|ab| max_a < ab.1).map(|&(a, b)| b).collect::<Vec<i64>>();
    bs.sort();

    let mut remain = h;
    let mut count = 0;
    for b in bs.iter().rev() {
        remain -= *b;
        count += 1;
        if remain <= 0 {
            return count
        }
    }

    let swing_count = {
        remain / max_a + if remain % max_a > 0 {1} else {0}
    };

    count + swing_count
}

fn main() {
    let (n, k) = parse_line!(usize, i64);
    println!("{}", solve(k, (0..n).map(|_| parse_line!(i64, i64)).collect()));
}

#[test]
fn solve_test() {
    assert_eq!(solve(10, vec![(3,5)]), 3);
    assert_eq!(solve(10, vec![(3,5), (2,6)]), 2);
    assert_eq!(solve(1000000000, vec![(1, 1), (1, 10000000), (1, 30000000),(1, 99999999)]), 860000004);
    assert_eq!(solve(500, vec![(35, 44), (28, 83), (46, 62), (31, 79), (40, 43)]), 9);
}


Measured memory_bytes: 6396
#include<iostream>
using namespace std;
int main(){
  int a,b,c,n,x[9999],y[9999],X[1000001],Y[1000001];
  a=b=c=1;
  while(1){
    x[a]=c*(c+1)*(c+2)/6;
    if(x[a]>1000000)break;
    a++;
    if(x[a-1]%2==1){
      y[b]=x[a-1];
      b++;
    }
    c++;
  }

  X[0]=0;
  for(int i=1;i<=1000000;i++)X[i]=i;
  for(int i=1;i<a;i++){
    for(int j=x[i];j<=1000000;j++){
      if(X[j]>X[j-x[i]]+1)X[j]=X[j-x[i]]+1;
    }
  }

  Y[0]=0;
  for(int i=1;i<=1000000;i++)Y[i]=i;
  for(int i=1;i<b;i++){
    for(int j=y[i];j<=1000000;j++){
      if(Y[j]>Y[j-y[i]]+1)Y[j]=Y[j-y[i]]+1;
    }
  }
  while(1){
    cin>>n;
    if(n==0)break;
    cout<<X[n]<<' '<<Y[n]<<endl;
  }
  return 0;
}

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

int main(){
  long long N;
  cin >> N;
  long long ans = 0;
  if (N%2==0){
    N /= 10;
    ans += N;
    while(N>0){
      N /= 5;
      ans += N;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
uppers = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
lowers = 'abcdefghijklmnopqrstuvwxyz'
s = str(input())
for i in range(len(s)):
    if s[i] in uppers:
        print(s[i].lower(), end='')
    elif s[i] in lowers:
        print(s[i].upper(), end='')
    else:
        print(s[i], end='')
print('')

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

public class Main {
	static final int MOD = (int)1e9+7;

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

		solve(sc,out);

		out.flush();
	}

	public static void solve(FastScanner sc, PrintWriter out) {
		int n = sc.nextInt();
		
		int[] a = sc.nextIntArray(n);
		
		int res = 0;
		
		int tmp = 1;
		
		for(int i = 0; i < n - 1; i++) {
			if(a[i] == a[i + 1]) {
				tmp++;
			}else{
				res+=tmp/2;
				tmp=1;
			}
		}
		
		out.println(res + tmp/2);
	}

	public static long gcd(long a, long b) {
		if(a < b) return gcd(b, a);
		if(b == 0) return a;
		return gcd(b, a % b);
	}

	public static long lcm(long a, long b) {
		return a / gcd(a, b) * b;
	}

	public static long factorial(int n) {
		long a;

		if(n > 0) {
			a = n * factorial(n - 1);
		}else{
			a = 1;
		}

		return a;
	}
}

class Pair<K, V> extends AbstractMap.SimpleEntry<K, V> {

    public Pair(K key, V value) {
        super(key, value);
    }

    public Pair<V, K> swap() {
    	return new Pair<V, K>(getValue(), getKey());
    }
 }

class UnionFind {
	int[] par;

	public UnionFind(int n) {
		par = new int[n];

		Arrays.fill(par, -1);
	}

	int root(int x) {
		if(par[x] < 0) return x;
		return par[x] = root(par[x]);
	}

	boolean unite(int x,int y) {
		x = root(x);
		y = root(y);

		if(x == y) return false;

		if(size(x) < size(y)) {
			int tmp = x;
			x = y;
			y = tmp;
		}

		par[x] += par[y];
		par[y] = x;

		return true;
	}

	boolean same(int x,int y) {
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}

	int size(int a) {
		return -par[root(a)];
	}
}

class FastScanner {
    private BufferedReader reader = null;
    private StringTokenizer tokenizer = null;

    public FastScanner(InputStream in) {
        reader = new BufferedReader(new InputStreamReader(in));
        tokenizer = null;
    }

    public String next() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public String nextLine() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        return tokenizer.nextToken("\n");
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public double nextDouble() {
         return Double.parseDouble(next());
     }

    public int[] nextIntArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = nextInt();
        return a;
    }

    public long[] nextLongArray(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++)
            a[i] = nextLong();
        return a;
    }
}

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

using namespace std;

typedef long long ll;
typedef pair< ll, ll > pll;
typedef pair< int, int > pii;

const double pi = 3.14159265358979323846;

#define MOD 1000000007LL
#define PS(p) cout << setprecision(15) << fixed << p << endl;
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
#define ALL(c) c.begin(), c.end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define TG0 get< 0 >
#define TG1 get< 1 >
#define TG2 get< 2 >
#define F first
#define S second
#define VL vector< ll >

// to_string(123)
// atoi("123"); atoi(s.c_str());
// "abc".size()
// s.find('+') == string::npos

ll w[100005];
ll v[105];
ll dp[105][100005];

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

  ll N, W;
  cin >> N >> W;

  for (ll i = 0; i < N; i++) {
    cin >> w[i] >> v[i];
  }

  for (ll i = 0; i < N; i++) {
    for (ll sum = 1; sum <= W; sum++) {
      if (sum - w[i] >= 0) {
        dp[i + 1][sum] = max(
            dp[i][sum - w[i]] + v[i],
            dp[i][sum]);
      } else {
        dp[i + 1][sum] = dp[i][sum];
      }
    }
  }

  cout << dp[N][W] << endl;

  return 0;
}


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

using namespace std;
#define DBG(x)                         \
    (void)(cout << "L" << __LINE__     \
                << ": " << #x << " = " \
                << (x) << '\n')
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
typedef long long ll;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const long double PI = (acos(-1));
const long double EPS = 0.0000000001;
const int INF = 0x3f3f3f3f;
const int maxn = 1100000;

void run_case()
{
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    ll cur1 = max(a * c, b * d);
    ll cur2 = max(a * d, b * c);
    cout << max(cur1, cur2) << "\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setiosflags(ios::fixed) << setprecision(12);
    run_case();
    cout.flush();
    return 0;
}

Measured memory_bytes: 3596
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<stdbool.h>
#include<assert.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")
#define charsize 100005 //10^5+5

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

int main(void){
    // char ;
    ll n,m;
    scanf("%lld%lld",&n,&m);
    ll a,sum=0;
    rep(i,0,m){
        scanf("%lld",&a);
        sum+=a;
    }
    if(sum>n){
        printf("-1\n");
    }else{
        printf("%lld\n",n-sum);
    }

    
    // printf("%lld\n");
    return 0;
}


Measured memory_bytes: 1708
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    vector<vector<int>> dp(n / 2 + 1, vector<int>(2, 1145141919));
    dp[1][0] = 0;

    for (int i = 1; i < n; i++) {
        for (int x = i; x >= 0; x--) {
            int y = i - x;
            if (x > n / 2 || y > n / 2)continue;

            if (x + 1 <= n / 2)dp[x + 1][0] = min(dp[x][0], dp[x][1] + cut[i - 1]);
            if (y + 1 <= n / 2) dp[x][1] = min(dp[x][0] + cut[i - 1], dp[x][1]);
        }
    }

    cout << min(dp[n / 2][0], dp[n / 2][1]) << endl;
    return 0;
}


Measured memory_bytes: 3304
import sys

a, b, c = map(int, sys.stdin.readline().strip().split(" "))
k = int(sys.stdin.readline().strip())

m = a
others = b + c

if m < b:
    m = b
    others = a + c
if m < c:
    m = c
    others = a + b

print(m * (2 ** k) + others)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(x) x.begin(), x.end()
#define mod 1000000007
typedef long long ll;

int main() {
    int a;
    cin >> a;
    cout << a + a*a + a*a*a << endl;
    return 0;
}

Measured memory_bytes: 3564
#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define ll long long
#define pb push_back
#define PII pair<int,int>
#define X first
#define Y second
#define MP make_pair
#define PI acos(-1.0)
#define eps 1e-8
const int maxn=5e3+10;
const int mod=1e9+7;
using namespace std;
int main(){
    int T;
//    scanf("%d",&T);
//    while(T--){
        int n;
        scanf("%d",&n);
        int flag=0;
        int cnt=0;
        for(int i=0;i<n;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            if(x==y){
                cnt++;
            }
            else
                cnt=0;
            if(cnt>=3)
                flag=1;
        }
        if(flag)
            printf("Yes\n");
        else
            printf("No\n");
 //   }
    return 0;
}


Measured memory_bytes: 3752
S = list(input())
S = [int(i) for i in S]

for i in range(2 ** 3):
    p = S[0]
    for j in range(3):
        if ((i >> j) & 1):
            p -= S[j+1]
        else:
            p += S[j+1]
    if p == 7:
        ans = str(S[0])
        for j in range(3):
            if ((i >> j) & 1):
                ans += '-'+str(S[j+1])
            else:
                ans += '+'+str(S[j+1])
        ans += '=7'
        print(ans)
        break


Measured memory_bytes: 3064
use proconio::input;
 
fn main() {
  input! {
    n: u64
  }
  
  let mut result: u64 = 0;

  for i in 1..=n {      
    if i % 3 != 0 && i % 5 != 0 {
      result += i;
    }
  }
  
  println!("{}", result);
}

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

int const mod = 1e9 + 7;
int dp[101][4][4][4];
signed main(void)
{
	int n;
	cin >> n;
	dp[0][3][3][3] = 1;
	rep(len, n)
	{
		// �Ōォ��1�����ڂ̕���
		rep(c1, 4)
		{
			// �Ōォ��2�����ڂ̕���
			rep(c2, 4)
			{
				// �Ōォ��3�����ڂ̕���
				rep(c3, 4)
				{
					 if (dp[len][c1][c2][c3] == 0) continue;
					 rep(a, 4)
					 {
						 if (a == 2 && c1 == 1 && c2 == 0) continue;
						 if (a == 2 && c1 == 0 && c2 == 1) continue;
						 if (a == 1 && c1 == 2 && c2 == 0) continue;
						 if (a == 2 && c1 == 1 && c3 == 0) continue;
						 if (a == 2 && c2 == 1 && c3 == 0) continue;

						 // S = ...c3 c2 c1
						 // nextS = ...c2 c1 a
						 dp[len + 1][a][c1][c2] += dp[len][c1][c2][c3];
						 dp[len + 1][a][c1][c2] %= mod;
					 }
				}
			}
		}
	}
	int ans = 0;
	rep(c1, 4)
	{
		rep(c2, 4)
		{
			rep(c3, 4)
			{
				ans += dp[n][c1][c2][c3];
				ans %= mod;
			}
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3648