akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bits/stdc++.h>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <vector>

// lib/util.hpp
#ifndef UTIL_HPP
#define UTIL_HPP


typedef ::std::int_fast64_t i64;
typedef ::std::uint_fast64_t u64;
typedef ::std::int_fast32_t i32;
typedef ::std::uint_fast32_t u32;

namespace tools {
  template <typename T>
  void read(::std::istream& is, ::std::vector<T>& vector, const typename ::std::vector<T>::size_type size) {
    vector.reserve(size);
    ::std::copy_n(::std::istream_iterator<T>(is), size, ::std::back_inserter(vector));
  }
  template <typename T>
  void read(::std::vector<T>& vector, const typename ::std::vector<T>::size_type size) {
    ::tools::read(::std::cin, vector, size);
  }

  template <typename T, ::std::size_t N>
  void read(::std::istream& is, ::std::array<T, N>& array) {
    ::std::copy_n(std::istream_iterator<T>(is), N, array.begin());
  }
  template <typename T, ::std::size_t N>
  void read(::std::array<T, N>& array) {
    ::tools::read(::std::cin, array);
  }
}

#endif

// main.cpp

int main() {
  i64 N;
  std::cin >> N;
  std::cout << (N - 1) * N / 2 << std::endl;
  return 0;
}

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

int main(void)
{
    int d,t,s;
    cin>>d>>t>>s;
    if(s*t>=d) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

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

typedef long long int ll;

int main () {
    int N;
    cin >> N;
    vector<int> v(N);
    for (auto& i : v) cin >> i;

    ll sum = 0LL;
    for (int i = 0, m = 0; i < N; i++) {
        if (m == v[i] - 1) {
            m = v[i];
            continue;
        }

        sum += (ll)((v[i] - 1) / (m + 1));

        if ((v[i] - 1) / (m + 1) == 0) {
            m = max(m, v[i]);
        }

        m = max(m, 1);
    }

    cout << sum << endl;

    return 0;
}


Measured memory_bytes: 640
import sys
input = sys.stdin.readline
from collections import defaultdict

N = int(input())
tmp = [int(i) for i in input().split()]
if tmp[0] != 0:
    print(0)
    exit()
D = defaultdict(int)
for i in tmp:
    D[int(i)] += 1
D_len = max(tmp)

MOD = 998244353

if D[0] != 1:
    print(0)
    exit()

answer = 1
for i in range(1,D_len+1):
    if D[i] == 0:
        answer = 0
        break
    tmp = 1
    for _ in range(D[i]):
        tmp = (tmp * D[i-1]) % MOD
    answer = (answer * tmp) % MOD

print(answer)

Measured memory_bytes: 20000
while True:
    a, s, b = input().split()
    if s == '?':
        break
    a, b = int(a), int(b)
    if s == '+':
        print(a + b)
    if s == '-':
        print(a - b)
    if s == '*':
        print(a * b)
    if s == '/':
        print(a // b)


Measured memory_bytes: 5596
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
#define double long double
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef vector<pii> VP;
typedef vector<string> VS;
typedef priority_queue<int> PQ;
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
#define eps 1e-12 
//priority_queue<int,vector<int>, greater<int> > q2;



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

	int N; cin >> N;
	VI L(N), R(N);
	REP(i, N)cin >> L[i] >> R[i];
	rSORT(L);
	SORT(R);
	VI sumL(N + 1, 0), sumR(N + 1, 0);
	REP(i, N) {
		sumL[i + 1] = sumL[i] + L[i];
		sumR[i + 1] = sumR[i] + R[i];
	}

	int ans = -INF;
	eREP(i, N) {
		int cnt = 2 * sumL[i];
		int tmp = cnt - sumR[i] * 2;
		chmax(ans, tmp);
		if (i != 0) {
			tmp = cnt - sumR[i - 1] * 2;
			chmax(ans, tmp);
		}
		if (i != N) {
			tmp = cnt - sumR[i + 1] * 2;
			chmax(ans, tmp);
		}
	}



	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 6344
N=gets.to_i
a=gets.split.map(&:to_i)
dp=[]
dp[0]=0
dp[1]=(a[0]-a[1]).abs
for i in 2..N-1
    dp[i]=[dp[i-1]+(a[i-1]-a[i]).abs,dp[i-2]+(a[i-2]-a[i]).abs].min
end
puts dp[N-1]

Measured memory_bytes: 13060
#include <iostream>
#include <functional>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <queue>
#include <map>
#include <iomanip>
#include <complex>
#include <random>
#include <bitset>
#include <list>
// #include <prettyprint.hpp>
using namespace std;
#define repi(i,n) for(int i=0;i<n;++i)
#define rep(i,n) for(ll i=0;i<n;++i)
#define repinvi(i,n) for(int i=n-1;i>=0;--i)
#define sll(n) scanf("%lld", &n);
#define sii(n) scanf("%d", &n);
#define slf(n) scanf("%lf", &n);
#define pll pair<ll,ll>
#define pii pair<int,int>
#define psi pair<si,si>
typedef long long ll;
typedef double lf;
typedef short int si;

class DisjointSet{
    public:
        vector<int> rank, p;

        DisjointSet(){}
        DisjointSet(int size){
            rank.resize(size, 0);
            p.resize(size, 0);
            for(int i=0;i<size;i++){
                makeSet(i);
            }
        }

        void makeSet(int x){
            p[x] = x;
            rank[x] = 0;
        }

        bool same(int x, int y){
            return findSet(x) == findSet(y);
        }

        void unite(int x, int y){
            link(findSet(x), findSet(y));
        }

        void link(int x, int y){
            if(rank[x]>rank[y]){
                p[y] = x;
            }else{
                p[x] = y;
                if(rank[x] == rank[y]){
                    rank[y] ++;
                }
            }
        }

        int findSet(int x){
            if(x!=p[x]){
                p[x] = findSet(p[x]);
            }
            return p[x];
        }
};


void Main(){
    ll N, M, K, a, b;
    sll(N);
    sll(M);
    sll(K);
    DisjointSet ds(N);
    map<ll, set<ll>> friends;
    map<ll, set<ll>> blocks;
    rep(i, M){
        sll(a);
        sll(b);
        -- a;
        -- b;
        ds.unite(a, b);
        friends[a].insert(b);
        friends[b].insert(a);
    }
    rep(i, K){
        sll(a);
        sll(b);
        -- a;
        -- b;
        blocks[a].insert(b);
        blocks[b].insert(a);
    }

    set<ll> ok;
    map<ll, set<ll>> groups;
    rep(i, N){
        ll parent = ds.findSet(i);
        groups[parent].insert(i);
    }

    map<ll,ll> ans;

    for(auto p:groups){
        // ll t_size = p.second.size() * (p.second.size() - 1) / 2;

        for(auto c:p.second){
            ll friend_num = 0;
            ll block_num = 0;
            for(auto c2:friends[c]){
                friend_num += p.second.find(c2) != p.second.end();
            }
            for(auto c2:blocks[c]){
                block_num += p.second.find(c2) != p.second.end();
            }
            ans[c] = p.second.size() - (friend_num + block_num) - 1;
        }
    }

    rep(i, N){
        printf("%lld", ans[i]);
        if(i< N-1){
            printf(" ");
        }
    }
    printf("\n");


}

int main(){
    Main();
}

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

#define FOR(i, j, k) for (int i = j; i < k; i++)
#define REP(i, j) FOR(i, 0, j)
#define RFOR(i, k, j) for (int i = k - 1; i >= j; i--)
#define RREP(i, j) RFOR(i, j, 0)
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<pii> vpii;

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

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

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

int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout << fixed;

    string s, t;
    cin >> s >> t;

    int ans = 0;
    REP(i, 3) {
        if (s[i] == t[i]) ans++;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
package main

import (
  "fmt"
  "strings"
  "unicode"
)

func main() {
  var s string 
  fmt.Scan(&s)
  res := "AC"
  if s[0] == 'A' {
    i := strings.Index(s, "C")
    if i == -1 || i == 1 || i == len(s) - 1 {
      res = "WA"
    } else {
      for j := 1; j < len(s); j++ {
        if j == i {continue}
        if rune(s[j]) != unicode.ToLower(rune(s[j])) {
          res = "WA"
          break
        }
      }
    }
  } else {
    res = "WA"
  }
  fmt.Println(res)
}

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

using namespace std;

int main()
{
	int H, W;
  	vector<string> a;
  
  	cin >> H >> W;
  
  	a.resize(H);
  
  	for(int i=0; i<H; i++)
    {
      	cin >> a[i];
      
      	a[i].insert(a[i].begin(), '#');
      	a[i].push_back('#');
    }
  
  	string s(W+2, '#');
  
  	a.insert(a.begin(), s);
  	a.push_back(s);
  
  	for(int i=0; i<a.size(); i++){
     cout << a.at(i) << endl; 
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, m, n) for(int i = m; i < (n); i++)
#define print(x) cout << x << endl;
#define printv(x) for(int i = 0; i < x.size(); i++){ cout << (x[i]) << " "; } cout << endl; 
#define printa(x) for(int i = 0; i < (sizeof(x)/sizeof(x[0])); i++){ cout << (x[i]) << " ";} cout << endl;

typedef long long ll;

using namespace std;

int main(){
    int N;
    cin >> N;
    int count_min = 10000000;
    rep(i,1,N){
        int ans = 0;
        string a = to_string(i);
        string b = to_string(N-i);
        rep(j,0,a.size()){
            ans += a[j] - '0';
        }
        rep(j,0,b.size()){
            ans += b[j] - '0';
        }
        count_min = min(count_min,ans);
    }
    print(count_min);

    cin.tie(0);
    ios::sync_with_stdio(false);
}


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

static class Extensions
{
    public static int ToInt(this string s) => int.Parse(s);
    public static long ToLong(this string s) => long.Parse(s);
    public static char ToChar(this string s) => char.Parse(s);
    public static double ToDouble(this string s) => double.Parse(s);
    public static int[] ToIntArray(this string s) => s.Replace(',', ' ').Split(' ').Select(x => x.ToInt()).ToArray();
    public static long[] ToLongArray(this string s) => s.Replace(',', ' ').Split(' ').Select(x => x.ToLong()).ToArray();
    public static double[] ToDoubleArray(this string s) => s.Replace(',', ' ').Split(' ').Select(x => x.ToDouble()).ToArray();
    public static Queue<T> ToQueue<T>(this IEnumerable<T> seq) => new Queue<T>(seq);
    public static Stack<T> ToStack<T>(this IEnumerable<T> seq) => new Stack<T>(seq);
    public static HashSet<T> ToHashSet<T>(this IEnumerable<T> seq) => new HashSet<T>(seq);
}
static class MyMath
{
    static private long gcdInner(long a, long b) => (a % b == 0) ? b : gcdInner(b, a % b);
    static public long GCD(long a, long b) => (a > b) ? gcdInner(a, b) : gcdInner(b, a);
    //static public long GCD(long a, long b) => (a < b) ? GCD(b, a) : ((a % b == 0) ? b : GCD(b, a % b));
    static public long LCM(long a, long b) => (a > b) ? (a / GCD(a, b) * b) : (b / GCD(a, b) * a);
    static private readonly long _m = 1000000000 + 7;
    static public long Mod(long val) => (val % _m + _m) % _m;
    static private long extGCD(long a, long b, ref long x, ref long y) => (b == 0) ? (a + (x = 1) * 0 + (y = 0) * 0) : (extGCD(b, a % b, ref y, ref x) + (y -= a / b * x) * 0);
    static public long ModInverse(long a, long dummy1 = 0, long dummy2 = 0) => extGCD(a, _m, ref dummy1, ref dummy2) * 0 + Mod(dummy1);    
}

class Program
{
    static string[] ReadLines(int n) => Enumerable.Range(0, n).Select(s => Console.ReadLine()).ToArray();

    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        int[] AList = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();

        int[] GCD_Ruiseki_L = new int[N];
        int[] GCD_Ruiseki_R = new int[N];

        //Lには、i番目よりも左側にある数のGCDをiに入れる。
        //Rには、i番目よりも右側にある数のGCDをiに入れる。

        for (int i = 1; i < N; i++)
        {
            GCD_Ruiseki_L[i] = getGCD(GCD_Ruiseki_L[i - 1], AList[i - 1]);
            GCD_Ruiseki_R[N - 1 - i] = getGCD(GCD_Ruiseki_R[N - 1 - i + 1], AList[N - 1 - i + 1]);
        }

        Console.WriteLine(Enumerable.Range(0, N).Max(n => getGCD(GCD_Ruiseki_R[n], GCD_Ruiseki_L[n])));
    }

    static int getGCD(int num1, int num2)
    {
        if (num1 < num2)
        {
            var tmp = num1;
            num1 = num2;
            num2 = tmp;
        }

        if (num2 == 0)
        {
            return num1;
        }
        int rem;
        Math.DivRem(num1, num2, out rem);

        return getGCD(num2, rem);
    }
}

Measured memory_bytes: 29020
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for (ll i = 0; i < (ll)n; i++)
#define all(x) (x).begin(), (x).end()
#define unique(x) x.erase(unique(x.begin(), x.end()), x.end());
const long long INF = 1LL << 60;
// map<int,int> mp;

int main() {
  ll a,b,c,d;
  cin >> a>>b>>c>>d;
  
  ll ans=-1000000000000000000;

ans = max(ans,a*c);
ans = max(ans,a*d);
ans = max(ans,b*c);
ans = max(ans,b*d);

cout << ans << endl;

}

Measured memory_bytes: 3620
import java.util.*; 

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

		String s = sc.next();
		if(s.charAt(0) >= 'a' && s.charAt(0) <= 'z'){
			System.out.println("a");
		 } else {
			 System.out.println("A");
		 }

		}
	  }

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

#define lli long long int
#define mod 1000000007

int main(){
	lli n,W;
	cin>>n>>W;
	lli a[n],w[n];
	for(int i=0;i<n;i++){
		cin>>w[i]>>a[i];
	}
	lli dp[n+1][W+1];
	for(int i=0;i<=n;i++){
		for(int j=0;j<=W;j++){
			if(i==0||j==0){
				dp[i][j]=0;
			}else if(w[i-1]<=j){
				dp[i][j]=max(a[i-1]+dp[i-1][j-w[i-1]],dp[i-1][j]);
			}else{
				dp[i][j]=dp[i-1][j];
			}
		}
	}
	cout<<dp[n][W]<<endl;
}

Measured memory_bytes: 79104
import sys
sys.setrecursionlimit(100000)
V, E = int(input()), int(input())
L = []
visited = [0 for i in range(V)]
edges = [[] for i in range(V)]
#flag = 0

def visit(x):
#  if visited[x] == 1:
#    flag = 1
  if not visited[x]:
    visited[x] = 1
    for e in edges[x]:
      visit(e)
    L.insert(0,x)

for i in range(E):
  s, t = map(int,input().split())
  edges[s - 1].append(t - 1)

for i in range(V):
  if not visited[i]:
    visit(i)

flag = 0
for i in range(V):
  print(L[i] + 1)
  if not flag and i < V - 1 and (L[i + 1] not in edges[L[i]]):
    flag = 1
print(flag)


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

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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tiii;
typedef pair<ll, ll> pll;

const int INF = 100000000;
const ll LINF = 1e18+5;


ll gcd(ll a, ll b) {
    if (b==0) return a;
    return gcd(b, a%b);
}

// return gcd(a,b) and solve ax+by=1
ll extgcd(ll a, ll b, ll& x, ll& y) {
    int d = a;
    if (b != 0) {
        d = extgcd(b, a%b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1;
        y = 0;
    }
    return d;
}

int main() {
    ll N, M;
    ll A[100000] = {};
    cin >> N >> M;
    rep(i,N) {
        cin >> A[i];
    }
    ll LCM = 1;
    ll GCD = 1;
    rep(i,N) {
        if(A[i]%2==1) {
            cout << 0 << endl;
            return 0;
        }
        A[i]/=2;
    }
    rep(i,N){ 
        LCM = gcd(GCD, A[i]);
        GCD = GCD * A[i] / LCM;
    }
    ll ans = 0;
    ll B[100000] = {};
    rep(i,N) {
        B[i] = (GCD / A[i]) % 2;
    }
    bool kflag = true;
    rep(i,N){
        if(B[i]==0) kflag = false;
    }
    if(kflag) {
        cout << ((M/GCD)+1)/2 << endl;
    } else {
        cout << 0 << endl;
    }
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>                                             
using namespace std;                                            
                                                                
int main() {                                                    
  int a, b;                                                     
  cin >> a >> b;                                                
  if (a<b) {                                                    
    cout << "a < b" << endl;                                    
  } else if (a>b) {                                             
    cout << "a > b" << endl;                                    
  } else {                                                      
    cout << "a == b" << endl;                                   
  }                                                             
  return 0;                                                     
}                                                               
                      

Measured memory_bytes: 3008
#![allow(unused_imports)]
use itertools::Itertools;
use proconio::{input, marker::*};
use std::cmp::*;
use std::collections::*;
use superslice::*;

fn main() {
    input! {
        a: u64,
        b: String,
    }

    let b = b.replace(".", "").parse::<u64>().unwrap();
    let ans = a * b / 100;
    println!("{}", ans);
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define MOD 1000000007

typedef long long int ll;

const ll INF=(ll)1e18;
//const int INF=(1<<30);


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

  vector<set<int> > ss(26);

  REP(i,s.size()){
    int t =  s[i] - 'a';
    ss[t].insert(i);
  }

  int q;
  cin >> q;
  REP(i,q){
    int type;
    cin >> type;
    if(type==1){
      int t;
      char c;
      cin >> t >> c;
      t--;
      ss[s[t] - 'a'].erase(t);
      s[t] = c;
      ss[s[t] - 'a'].insert(t);
    }else{
      int l,r;
      cin >> l >> r;
      l--;r--;
      int ans=0;
      REP(j,26){
        if(ss[j].upper_bound(r)!=ss[j].lower_bound(l)){
          ans++;
//          cout << j << ":" << endl;
        }else{
        }
      }
      cout << ans << endl;
    }
  }

}



Measured memory_bytes: 24196
#include<bits/stdc++.h>
using namespace std;
bool comp(pair<long long int,long long int>a,pair<long long int,long long int>b)
{
    if(a.first==b.first)
    {
        if(a.second<=b.second)
        return true;
        else
        return false;
    }
    if(a.first>b.first)
    return true;
    else return false;
}
long long int gcd(long long int bdda,long long int chota)
{
    if(chota==0)
        return bdda;
    return gcd(chota,bdda%chota);
}
void solve()
{
    long long int a,b;
    cin>>a>>b;
    long long int ans=0,o=1;
    while(o<b)
    {
        ans++;
        o--;
        o+=a;
    }
    cout<<ans<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;    
    t=1;

    //cin>>t;
    while(t--)
    {
        solve();
    }
}


Measured memory_bytes: 3600
def check(cx, cy, t, x, y):
    dx = abs(x - cx)
    dy = abs(y - cy)
    if dx + dy > t:
        return False
    if ((dx + dy) & 1) != (t & 1):
        return False
    return True


n = int(input())
ct, cx, cy = 0, 0, 0
for _ in range(n):
    t, x, y = map(int, input().split())
    result = check(cx, cy, t - ct, x, y)
    if not result:
        print('No')
        break
    ct, cx, cy = t, x, y
else:
    print('Yes')


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
int main(){
	ll a,b,d;
	cin>>a>>b>>d;
	ll c=0;
	for(ll i=a;i<=b;i++){
		if(i%d==0){
			c++;
		}
	}
	
	cout<<c;
	
	
	return 0;
}

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

#define FOR(i, a, b) for(int i = a; i<b; ++i)
#define FR(a, b) for(int i = a; i>=b;--i)
#define _upgrade cin.tie(0); ios_base::sync_with_stdio(0)
#define pb push_back
#define mp make_pair
#define INF 1e9+2137
#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef pair<int, int> iPair;

const int MAX = 1e5+1;
const int M = 1e9+7;

vector<int> G[MAX];
int n, m, dp[MAX], degree[MAX];
int main()
{
    _upgrade;
    cin>>n>>m;
    FOR(i, 0, m)
    {
        int a, b;
        cin>>a>>b;
        G[a].pb(b);
        degree[b]++;
    }
    stack<int> S;
    FOR(i, 1, n+1)
        if(!degree[i])
            S.push(i);

    while(!S.empty())
    {
        int v = S.top();
        S.pop();
        for(int i : G[v])
        {
            dp[i] = max(dp[i], dp[v]+1);
            degree[i]--;
            if(!degree[i])
                S.push(i);
        }
    }
    int res = 0;
    FOR(i, 1, n+1)res = max(res, dp[i]);
    cout<<res;
}


Measured memory_bytes: 6528
#include <cstdio>

int line[10001];

int main(){
	int n;
	line[1] = 2;
	for(int i = 2; i < 10001; i++) {
		line[i] = line[i-1] + i;
	}
	while(scanf("%d", &n) != EOF){
		printf("%d\n", line[n]);
	}
	return 0;
}

Measured memory_bytes: 1060
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds; 
using namespace std;
template<class T> using rset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; 

using ll = long long;
using db = double;
using vi = vector<int>;
const int maxn = 1000000; 

ll n, k; 
ll a[maxn], s[maxn]; 
rset<pair<ll,int>> S; 

int main() {
	cin>>n>>k; 
	s[0] = 0; 
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]); 
		s[i] = s[i-1]+a[i]-k; 
	}
	S.insert({s[0],0}); 
	ll ans = 0; 
	for (int i = 1; i <= n; ++i) {
		S.insert({s[i],i}); 
		ans += S.order_of_key({s[i],i});
	}
	cout<<ans<<endl; 
}


Measured memory_bytes: 18432
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define loop(i,n) rep(i,0,n)
using namespace std;
using ll = long long;
template<typename weight_t> using graph = vector<vector<pair<int,weight_t>>>;
template<typename weight_t> vector<weight_t> dijkstra(const graph<weight_t> &g,const int e){
    using node=pair<int,weight_t>; auto cmp=[](node &a,node &b)->bool {return (a.second>b.second);};
    priority_queue<node,vector<node>,decltype(cmp)> pq(cmp);
    vector<weight_t> w(g.size(),numeric_limits<weight_t>::max());
    pq.push({e,0}); w[e]=0;
    while(!pq.empty()){ auto u=pq.top(); pq.pop();
        for(auto &v:g[u.first])if(w[u.first]+v.second<w[v.first]){ w[v.first]=w[u.first]+v.second; pq.push({v.first,w[v.first]}); }}
    return w;
}
int main(){
    double xs,ys,xt,yt;
    int n;
    cin >> xs >> ys >> xt >> yt >> n;
    vector<double> x(n+2),y(n+2),r(n+2);
    x[0]=xs;
    y[0]=ys;
    x[1]=xt;
    y[1]=yt;
    rep(i,2,n+2){
        cin >> x[i] >> y[i] >> r[i];
    }
    graph<double> g(n+2);
    loop(i,n+2)g[i].reserve(n+2);
    auto dist = [&](double xi,double yi,double xj,double yj)->double{
        return sqrt((xi-xj)*(xi-xj)+(yi-yj)*(yi-yj));};
    loop(i,n+1)rep(j,i+1,n+2){
        double d=max(0.0,dist(x[i],y[i],x[j],y[j])-r[i]-r[j]);
        g[i].push_back({j,d});
        g[j].push_back({i,d});
    }
    auto ans=dijkstra(g,0);
    cout << setprecision(10) << ans[1] << endl;
    return 0;
}

Measured memory_bytes: 21872
#include <stdio.h>

int main(void) {
	
	int w, lw = 4280;
	int w1 = 1150,
		w2 = 1250,
		w3 = 1400;
	
	while(1){
		scanf("%d", &w);
		if(w == -1)		break;
		
		if(w <= 10)			w = w1;
		else if(w <= 20)	w = w1 + (w - 10) * 125;
		else if(w <= 30)	w = w1 + w2 + (w - 20) * 140;
		else 				w = w1 + w2 + w3 + (w - 30) * 160;

		printf("%d\n", lw - w);
	}
	
	return 0;
}

Measured memory_bytes: 600
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <numeric>
typedef long long Int;
#define rep(i,a,b) for(Int i=a;i<b;++i)
#define rrep(i,a,b) for(Int i=a;i>=b;--i)
using namespace std;

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

    int H, W; cin >> H >> W;
    vector<string> C(H);
    rep(i, 0, H) cin >> C[i];
  
    rep(i, 0, H) {
      cout << C[i] << endl << C[i] << endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
using namespace std;
 
#define dump(x)  cout << #x << " = " << (x) << endl;
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) << endl
 
#define SANKOU(n,a,b) cout << ((n) ? (#a) : (#b) ) << endl
 
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
 
#define FOREACH(x,a) for(auto& (x) : (a) )
 
#define WFA(d,v) REP(k,v)REP(i,v)REP(j,v)d[i][j]=min(d[i][j],d[i][k]+d[k][j])
 
#define SCOUT(x) cout<<(x)<<" "
#define ENDL cout<<endl
 
#define VECCIN(x) for(auto&youso_: (x) )cin>>youso_
#define VECIN2(x,y) REP(i,x.size())cin>>x[i]>>y[i]
#define VECCOUT(x) for(auto&youso_: (x) )cout<<youso_<<" ";cout<<endl
 
#define ALL(obj) (obj).begin(),(obj).end()
 
#define EXIST(n,x) (find(ALL(n),x)!=n.end())
#define UNIQUE(obj) sort(ALL( obj )); obj.erase(unique(ALL(obj)),obj.end())
#define COUT(x) cout<<(x)<<endl
void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail){
    cin>>head;
    CINT(move(tail)...);
}
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)
 
//#include <boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision; // cpp_int
 
#define P pair<int,int>
#define V vector<ll>
#define M map<int,int>
#define S set<int>
#define L list<int>
 
#define pb(a) push_back(a)
#define mp make_pair

int main(){

  CIN(n);V a(n);VECCIN(a);
  ll ans=LINF;
  REP(tt,2){
    ll now=0;
    ll cost=0;
    REP(i,n){
      now+=a[i];
      if(tt==i%2){//なんかいい感じに1/2が出せそう？
        if(now<=0){//正の数に変える
          cost+=1-now;
          now=1;
        }
      }else{
        if(now>=0){
          cost+=now+1;
          now=-1;
        }
      }
    }
    ans=min(ans,cost);
  }
  COUT(ans);
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007
const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
int main() {
	ll n,k;
	cin>>n>>k;
	vector<ll>a;
	for(ll i=0;i<n;i++){
		ll x;
		cin>>x;
		a.push_back(x);
	}
	sort(a.begin(),a.end());
	COMinit();

    // 計算例
    ll mi=0,ma=0;
    for(ll i=0;i<n;i++){
    	if(n-(i+1)<k-1){
    		break;
    	}
    	ll now=COM(n-(i+1),k-1);
    	mi+=now*a[i];    	ma+=now*a[n-i-1];
    	mi%=inf;
    	ma%=inf;
    	if(mi<0){
    		mi+=inf;
    	}
    	if(ma<0){
    		ma+=inf;
    	}
    }
    ll ans=ma-mi;
    ans%=inf;
    if(ans<0){
    	ans+=inf;
    }
    cout << ans << endl;	
	// your code goes here
	return 0;
}

Measured memory_bytes: 13172
n,k=map(int,input().split())
a=list(map(int,input().split()))
l=[0]*(n-k)
for i in range(n-k):
    l[i]=a[i+k]/a[i]
for i in range(n-k):
    if l[i]>1:
        print("Yes")
    else:
        print("No")

Measured memory_bytes: 31684
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf  1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
ll gcd(ll v,ll b){
	if(v>b) return gcd(b,v);
	if(v==b) return b;
	if(b%v==0) return v;
	return gcd(v,b%v);
}
int main(){
    ll n,m;
    cin >> n >> m;
    string a,b;
    cin >> a >> b;
    ll k = gcd(n,m);
    ll ans = n*m/k;
    ll p = n/k;
    ll q = m/k;
    ll x = 0;
    bool flag =0;
    for(int i=0;i<n;i+=p){
        if(a[i]!=b[x]){
            flag = 1;
        }
        x+=q;
    }
    if(flag){
        cout << -1 << endl;
    }else{
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 888
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;

struct ss{
	ll a;
	ll b;
}s[100020];

bool cmp(ss aa,ss bb){
	return aa.b>bb.b;
}

int main()
{
	ios::sync_with_stdio(false);
	ll n,h;
	cin>>n>>h;
	int max=0;  //平a 最大
	int t=0;    //好刀的投掷

	for(int i=0;i<n;i++){
		cin>>s[i].a>>s[i].b;
	}
	sort(s,s+n,cmp);

	for(int i=0;i<n;i++){
		if(s[i].a>max){
			max=s[i].a;
			t=i;
		}
	}
	int yy=0;
	for(int i=0;i<n;i++){
		if(s[i].b>max){
			h=h-s[i].b;
			yy++;
			if(h<=0){
				cout<<yy<<endl;
				return 0;
			}
		}
	}

	if(h>0){
		yy+=ceil(h*1.0/max);
	}
	cout<<yy<<endl;
return 0;
}


Measured memory_bytes: 1792
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();//金額
      	
      while(n>0){
		n=n-1000;
      }
     
        System.out.println(-n); 
     
    } 
}










Measured memory_bytes: 35820
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll N = 2e5+5;
vector<int>adj[N],adj1[N];
vector<pair<int,int>>v;
map<pair<int,int>,int>mp;
bool visited[N];
int height[N],val[N],grid[55][55];

int dfs(int node){
    if(visited[node])return 0;
    visited[node]=true;
    for(auto i:adj[node]){
        val[node]+=dfs(i);
    }
    return val[node]+1;
}

void solve(){
 int n,m;
 cin>>n>>m;
 for(int i=0;i<m;i++){
    int u,v;
    cin>>u>>v;
    adj[u].push_back(v);
    adj[v].push_back(u);
 }
int ans=0;
 for(int i=1;i<=n;i++){
    if(!visited[i]){
        val[i]=dfs(i);
        ans=max(ans,val[i]);
    }
 }
cout<<ans;
}
int main(){
    int t=1;
    //cin>>t;
   while(t--)solve();
}


Measured memory_bytes: 29572
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

mia = sorted([i for i in a if i < 0], reverse=True)
pla = sorted([i for i in a if i >= 0])

cnt = 1
if len(pla) == 0 and k % 2 == 1:
    for i in mia[:k]:
        cnt = cnt * i % mod
    print(cnt)
    exit()

while k > 0:
    if k == 1 or len(mia) <= 1:
        if len(pla) == 0:
            cnt *= mia.pop()
        elif len(pla) > 0:
            cnt *= pla.pop()
        k -= 1
    elif len(pla) <= 1:
        cnt *= mia.pop() * mia.pop()
        k -= 2
    elif pla[-1] * pla[-2] > mia[-1] * mia[-2]:
        cnt *= pla.pop()
        k -= 1
    elif pla[-1] * pla[-2] <= mia[-1] * mia[-2]:
        cnt *= mia.pop() * mia.pop()
        k -= 2
    cnt %= mod
else:
    print(cnt)


Measured memory_bytes: 31624
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <math.h>
#include <string>
using namespace std;

int main()
{
//	freopen("input.txt","r",stdin);
  //  freopen("output.txt","w",stdout);
 	
 	int a=0;int b=0;
 	int n;
 	scanf("%d",&n);
 	vector<int> p(n);
 	vector<int> q(n);
 	std::vector<int> fact(n+1);
 	fact[0]=1;
 	bool pvis[n+1]={};
 	bool qvis[n+1]={};
 	for(int i=0;i<n;i++){
 		fact[i+1]=(i+1)*fact[i];
 		scanf("%d",&p[i]);
 	}
 	int atr,btr;
 	for(int i=0;i<n;i++){
 		scanf("%d",&q[i]);

 		int aa=0;int bb=0;
 		for(int j=1;j<=n;j++){
 			if(!pvis[j])aa++;
 			if(!qvis[j])bb++;
 			if(j==p[i]){
 				atr=aa-1;
 				pvis[j]=1;
 			}
 			if(j==q[i]){
 				btr=bb-1;
 				qvis[j]=1;
 			}	
 		}
 		a+=(atr*fact[n-i-1]);
 		b+=(btr*fact[n-i-1]);

 	}
 	printf("%d\n",abs(a-b) );

    return 0;
}
 

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

using namespace std;

typedef short sho;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
typedef string str; 
 
typedef pair<int,int> pii;
typedef pair<ll,ll> pll; 
typedef pair<ld,ld> pld;
 
typedef vector<int> vi; 
typedef vector<ll> vl; 
typedef vector<ld> vd;
typedef vector<str> vs;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef vector<pld> vpd;

#define mp make_pair 
#define FF first
#define SS second
#define sz(x) (int)x.size()
#define begin(x) (x).begin() 
#define end(x) (x).end()
#define rbegin(x) (x).rbegin()
#define rend(x) (x).rend()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pf push_front 
#define pb push_back
#define pp push
#define lb lower_bound 
#define ub upper_bound

int n;
int a[110];
int ans=1e9;

int main() {
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    /* start code */
    cin>>n;
    for(int i=0;i<n;i++)
    	cin>>a[i];
    for(int i=1;i<=100;i++)
    {
    	int sum=0;
    	for(int j=0;j<n;j++)
    	{
    		sum+=(a[j]-i)*(a[j]-i);
		}
		ans=min(ans,sum);
	}
	cout<<ans<<endl;
    /* end code */
	return 0;
}

Measured memory_bytes: 256
import java.io.*;

class Main {
    public static void main (String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Dice dice = new Dice(br.readLine().split(" "));
        String operations = br.readLine();

        for (int i = 0; i < operations.length(); i++) {
            dice.roll(operations.charAt(i));
        }

        System.out.println(dice.getTopFace());

    }
}

class Dice {
    private int[] dice = new int[6];

    Dice (String[] num) {
        for (int i = 0; i < 6; i++) {
            dice[i] = Integer.parseInt(num[i]);
        }
    }

    public void roll (char direction) {
        int temp;
        switch (direction) {
            case 'N':
            temp = dice[0];
            dice[0] = dice[1];
            dice[1] = dice[5];
            dice[5] = dice[4];
            dice[4] = temp;
            break;

            case 'S':
            temp = dice[0];
            dice[0] = dice[4];
            dice[4] = dice[5];
            dice[5] = dice[1];
            dice[1] = temp;
            break;

            case 'E':
            temp = dice[0];
            dice[0] = dice[3];
            dice[3] = dice[5];
            dice[5] = dice[2];
            dice[2] = temp;
            break;

            case 'W':
            temp = dice[0];
            dice[0] = dice[2];
            dice[2] = dice[5];
            dice[5] = dice[3];
            dice[3] = temp;
            break;
        }
    }

    public int getTopFace () {
        return dice[0];
    }
}

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

int main(){
    int l,r,d;
    int count=0;
    cin>>l>>r>>d;
    for(int i=l;i<r+1;i++){
        if(i%d==0)count++;
    }
    cout<<count<<endl;
    
}

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll N, K;
  cin >> N >> K;
  ld ans = 0;
  vector<ll> Xs;
  // iは目
  for(ll i = 1; i <= N; i++) {
    ll X = 0;
    while(1) {
      ll P = i * pow(2, X);
      if(P >= K) { break; }
      X++;
    }
    Xs.push_back(X);
    // cout << X << endl;
    // ld p = 1;
    // for(ll i = 0; i < X; i++) {
    // p /= 2.0;
    // }
    // ans += p / N;
    // cout << std::setprecision(30) << ans << endl;
  }
  sort(Xs.begin(), Xs.end());
  // ans /= N;
  ld bunbo = pow(2, Xs[Xs.size() - 1]);
  // cout << bunbo << endl;
  ld bunsi = 0;
  for(int i = 0; i <= Xs.size() - 1; i++) {
    bunsi += pow(2, Xs[Xs.size() - 1] - Xs[i]);
  }
  // cout << bunsi << endl;
  ans = bunsi / bunbo;
  ans /= N;
  cout << std::setprecision(30) << ans << endl;
  return 0;
}

Measured memory_bytes: 1400
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ll long long
#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 INF ((1LL<<62)-(1LL<<31))
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define bit(n,m)((n>>m)&1)
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);}
ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;}
//#define MOD 998244353
#define MOD 1000000007
#define invp(a,p)pom(a,p-2,p)

ll n,k;
ll a[1010];
ll cum[1010];
ll s[510010],cnt;

int main(){
	scanf("%lld%lld",&n,&k);
	rep(i,0,n){
		scanf("%lld",a+i);
		cum[i+1]=cum[i]+a[i];
		rep(j,0,i+1)s[cnt++]=cum[i+1]-cum[j];
	}

	ll ans=0;
	for(int i=45;i>=0&&cnt>=0;i--){
		sortdown(s,cnt);
		ll cc=0;
		rep(idx,0,cnt){
			if(bit(s[idx],i)){
				cc++;
				s[idx]^=(1LL<<i);
			}
			else break;
		}
		if(cc>=k){
			cnt=cc;
			ans|=(1LL<<i);
		}
	}
	printf("%lld",ans);
}

Measured memory_bytes: 8060
#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <string>
#include <iostream>
#include <stdio.h>
#include <queue>
#include <cmath>
#include <utility>
#include <map>

using namespace std;
typedef long long ll;
#define rep(i,a,b) for(int i=(a);i<(b);++i)



int main() {
	string S;
	cin >> S;
	int ans = 0;
	int i=0, j=S.size()-1;
	while (i < j) {
		if(S[i] == 'x' && S[j] == 'x') {
			i++;
			j--;
		}
		else if(S[i] == 'x') {
			ans++;
			i++;
		}
		else if(S[j] == 'x') {
			ans++;
			j--;
		}
		else if (S[i] == S[j]) {
			i++;
			j--;
		}
		else {
			cout << "-1";
			return 0;
		}

	}
	cout << ans;

	return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>
#include <set>
using namespace std;
using Int = long long;
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,f,t) for(int i=f;i<t;i++)
#define P(ary) do { for(auto i:ary){ cout << i << " "; } cout << endl; } while (0)
int main()
{
    int X, t; cin >> X >> t;
    cout << max(0, X-t) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;

const int mxint = 0x3fffffff, mxn = 500000 + 10;
int n;
char num[mxn];
int link[2][mxn], action[mxn];

// int getBig(int l, int r){
//     int numZero = 0,//l~r中0的个数
//         numOne = 0,//当前小段中1的个数
//         minOne = mxint;//最小的小段中1的个数
//     for(int i = l; i <= r; ++i){
//         if(num[i]){
//             ++numOne;
//         }
//         else{
//             ++numZero;
//             minOne = min(minOne, numOne);
//             numOne = 0;
//         }
//     }
//     return numOne - minOne - numZero + 2;
// }

void getAns(){
    memset(action, 0, sizeof(action));
    for(int i = 1; i < n - 1; ++i){
        action[i] = max(action[i], action[i - 1]);
        if(num[i]){
            if(num[link[0][i] - 1]){
                action[i] = max(action[i],
                                action[link[0][i] - 2] + i - link[0][i]);
            }
            if(num[link[1][i] + 1]){
                action[link[1][i] + 1] = max(action[link[1][i] + 1],
                                         action[i - 1] + link[1][i] - i);
            }
        }
    }
}
void pre(){
    int x = 0;
    for(int i = 0; i < n; ++i){
        if(num[i]){
            link[0][i] = x;
        }
        else{
            link[0][i] = i;
            x = i;
        }
    }
    x = n - 1;
    for(int i = n; i >= 0; --i){
        if(num[i]){
            link[1][i] = x;
        }
        else{
            link[1][i] = i;
            x = i;
        }
    }
}

int main(){

// 1111011110111101111
// 0000001110111101111 4
// 0000001110111000000 8
// 0000000000011000000 11
    scanf("%d\n", &n);
    n += 2;
    num[0] = num[1] = 0;
    for(int i = 2; i < n; ++i){
        num[i] = getchar() - '0';
    }
    n += 2;
    num[n - 1] = num[n - 2] = 0;
    pre();
    getAns();

    // for(int i = 0; i < n; ++i){
    //     cout<<i<<'\t';
    // }
    // cout<<endl;
    // for(int i = 0; i < n; ++i){
    //     cout<<(int)num[i]<<'\t';
    // }
    // cout<<endl;
    // for(int i = 0; i < n; ++i){
    //     cout<<action[i]<<'\t';
    // }
    // cout<<endl;
    // for(int i = 0; i < n; ++i){
    //     cout<<(int)link[0][i]<<'\t';
    // }
    // cout<<endl;
    // for(int i = 0; i < n; ++i){
    //     cout<<(int)link[1][i]<<'\t';
    // }
    // cout<<endl;

    printf("%d\n", action[n - 3]);
    return 0;
}


Measured memory_bytes: 6528
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <deque>
#include <ctime>
#include <map>
#include <set>

#define ll long long
#define inf 0x3f3f3f3f
#define il inline

namespace io {

#define in(a) a = read()
#define out(a) write(a)
#define outn(a) out(a), putchar('\n')

#define I_int ll
inline I_int read() {
    I_int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
char F[200];
inline void write(I_int x) {
    if (x == 0) return (void) (putchar('0'));
    I_int tmp = x > 0 ? x : -x;
    if (x < 0) putchar('-');
    int cnt = 0;
    while (tmp > 0) {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0) putchar(F[--cnt]);
}
#undef I_int

}
using namespace io;

using namespace std;

#define N 1000100

int n = read(), m = read();
struct node {
	ll a, b;
}a[N];

bool cmp(node a, node b){
	return a.a < b.a;
} 

int main() {
	int cnt = 0; ll ans = 0;
	for(int i = 1; i <= n; ++i) in(a[i].a), in(a[i].b);
	sort(a+1,a+n+1,cmp);
	for(int i = 1; i <= n; ++i) {
		if(cnt > m) break;
		ans += (ll)(min(a[i].b, (ll)m - cnt) * a[i].a);
		cnt += a[i].b;
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); ++i)
using namespace std;
using ll=long long;
int main(){
    int n;
    cin>>n;
    vector<int>x,b(n);
    rep(i,n)cin>>b[i];
    rep(i,n){
        if(b[i]-1>i){cout<<-1<<endl; return 0;}
        x.insert(x.begin()+b[i]-1,b[i]);
    }
    rep(i,n){
        cout<<x[i]<<endl;
    }
}

Measured memory_bytes: 256
import java.util.*;
class Main{
    public static void main(String[] args) {
        Scanner sc  = new Scanner (System.in);
        String s = sc.next();
        int len = s.length();
        boolean easyP = true;
        for(int i = 0;i<len;i++){
            if(i%2==0){
                if(s.charAt(i)=='R'||s.charAt(i)=='U'||s.charAt(i)=='D'){
                
                }
                else{
                    easyP = false;
                    break;
                }
        }
        if(i%2!=0){
            if(s.charAt(i)=='L'||s.charAt(i)=='U'||s.charAt(i)=='D'){
                
            }
            else{
                easyP = false;
                break;
            }
        }
        }
        System.out.println(easyP?"Yes":"No");
        }

       
    }


Measured memory_bytes: 35604
#include <iostream>
using namespace std;
long long N;
long long GCD(long long x, long long y)
{
    long long r = x % y;
    while(r > 0)
    {
        x = y;
        y = r;
        r = x % y;
    }
    return y;
}
void Solve()
{
    cin >> N;
    for(long long i = 1; i <= 3500; i++)
        for(long long j = 1; j <= 3500; j++)
        {
            long long nb = i + j;
            long long num = i * j;
            if(i == 2 && j == 80)
            {
                int po;
                po  = 0;
            }
            long long x = (N * num) / GCD(N, num);
            nb = 4 * num - nb * N;
            num = num * N;
            if(nb > 0 && num % nb == 0)
            {
                num /= nb;
                cout << i << " " << j << " " << num << "\n";
                return;
            }
        }
}
int main()
{
    Solve();
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args){
        //ArrayList<Integer> array = new ArrayList<Integer>();
        //Scanner sc = new Scanner(System.in);
        for(int i=1; i<10; i++){
            for(int j=1; j<10; j++){
                System.out.println(i + "x" + j + "=" + (i*j));
            }
        }
    }
}



Measured memory_bytes: 24116
n,k = map(int,input().split())         # n=町の個数 , k=テレポート回数
a_list = list(map(int,input().split()))     # 各町のテレポート先リスト
dum = a_list[0]                        # dum=次のテレポート先
k = k - 1                              # テレポート回数をデクリメント
ans_list = [1]                         # 訪れた町を ans_list に格納
ok = True
check_list = n*[0]
check_list[0] = 1
for i in range(k+1):
    if ok and check_list[dum-1] == 1:
        #print(dum,111)
        ind = ans_list.index(dum)
        loop = ans_list[ind:]
        len_loop = len(loop)
        k = k % len_loop
        ans_list = []
        ok = False
    else:
        check_list[dum-1] = 1

    if k == 0:
        print(int(dum))
        break
    ans_list.append(dum)
    dum = a_list[int(dum)-1]
    k = k - 1



Measured memory_bytes: 95472
#include<iostream>

using namespace std;

int main() {
    int a,b;
    cin >> a >> b;

    if (a < b) {
        cout << "a < b" << endl;

    }
    else if(a > b){
        cout << "a > b" << endl;

    }
    else {
        cout << "a == b" << endl;
    }
}


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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a,p; cin >> a >> p;
    cout << (3*a + p)/2 << endl;
}

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

using ll = long long;

using namespace std;

int main() {
    int k, n;
    cin >> k >> n;
    int dif = 0;
    int prev, first;
    cin >> prev;
    first = prev;
    for (int i=1, ai; i<n; i++) {
        cin >> ai;
        dif = max(dif, ai - prev);
        prev = ai;
    }
    cout << min(k - dif, prev - first) << '\n';
    return 0;
}

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

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

signed main() {
  ll N, M;
  cin >> N >> M;
  priority_queue<ll> q;
  rep(i,N) {
    ll x;
    cin >> x;
    q.push(x);
  }
  rep(i,M){
    auto t = q.top(); q.pop();
    q.push(t/2);
  }

  ll ans = 0;
  rep(i,N) {
    ans += q.top(); q.pop();
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1400
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T> void assign(V<T>& v, int n, const T& a = T()) { v.assign(n, a); }
template<class T, class... U> void assign(V<T>& v, int n, const U&... u) { v.resize(n); for (auto&& i : v) assign(i, u...); }

int main() {
  cin.tie(NULL); ios::sync_with_stdio(false);
  int n; cin >> n;
  V<> a(n); for (int i = 0; i < n; i++) cin >> a[i];
  bitset<(int) 4e6 + 1> dp;
  dp[0] = 1;
  for (int i = 0; i < n; i++) dp |= dp << a[i];
  for (int i = accumulate(a.begin(), a.end(), 1) / 2;; i++) if (dp[i]) return cout << i << '\n', 0;
}

Measured memory_bytes: 1792