akhauriyash/Code-Regression huggingface dataset:
# Reference: https://qiita.com/dn6049949/items/afa12d5d079f518de368

# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

class SegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, f=max, default=-10**18):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.f = f

    # a[i] = x
    # O(log(n))
    def update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

    # return f(a[l:r])
    # O(log(n))
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

    # You can use min_index only if f == max.
    # return min({i | x <= i and v <= a[i]}, self.num_leaf)
    # O(log(n))
    def min_index(self, x, v):
        x += self.num_leaf
        while self.data[x] < v:
            if x & 1: # x % 2 == 1
                if x.bit_length() == (x+1).bit_length():
                    x += 1
                else:
                    return self.num_leaf
            else:
                x >>= 1
        while x < self.num_leaf:
            if self.data[2*x] >= v:
                x = 2*x
            else:
                x = 2*x + 1
        return x - self.num_leaf

def main():
    from sys import stdin
    input = stdin.buffer.readline

    n, q = map(int, input().split())
    a = list(map(int, input().split()))

    st = SegmentTree(n=n, f=max, default=-1)
    for i, ai in enumerate(a):
        st.update(i, ai)

    for _ in range(q):
        t, x, v = map(int, input().split())
        if t == 1:
            st.update(x-1, v)
        elif t == 2:
            print(st.query(x-1, v))
        else:
            print(min(st.min_index(x-1, v), n) + 1)

main()


Measured memory_bytes: 94232
#include<iostream>
#define for0(i, n) for(int i = 0; i < (n); i++)
using namespace std;
signed main() {
	int x; cin >> x;
	for0(i, 1001) { if (i * 100 <= x && x <= i * 105) { cout << "1\n"; return 0; } }
	cout << "0\n";
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        
        var sc = new Scanner(System.in);
        
        int n = Integer.parseInt(sc.next());
        int xor = 0;
        var a = new int[n];
        for(int i = 0; i < n; i++){
            a[i] = Integer.parseInt(sc.next());
            xor ^= a[i];
        }
        
        var sb = new StringBuilder();
        for(int i = 0; i < n; i++){
            xor ^= a[i];
            sb.append(xor).append(" ");
            xor ^= a[i];
        }
        System.out.println(sb);
    }
}

Measured memory_bytes: 62012
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <tuple>
#include <bitset>
using namespace std;

typedef long long ll;
const ll MAX_N = 50 + 1;
const ll MOD_M = 1000000000 + 7;

auto matrix_product_mod(vector<vector<ll> > &mat_a, vector<vector<ll> > &mat_b, ll m, ll N) {

  vector<vector<ll> > mat_res(N, vector<ll>(N));

  for (ll i = 0; i < N; i++) {
    for (ll j = 0; j < N; j++) {
      ll temp = 0;
      for (ll k = 0; k < N; k++) {
	temp += mat_a[i][k] * mat_b[k][j];
	temp %= m;
      }
      mat_res[i][j] = temp;
    }
  }
  
  return mat_res;
}

auto matrix_binpow_mod(vector<vector<ll> > &mat_a, ll n, ll m, ll N) {

  vector<vector<ll> > mat_res(N, vector<ll>(N));

  for (ll i = 0; i < N; i++) {
    for (ll j = 0; j < N; j++) {
      if (i == j) mat_res[i][j] = 1;
      else mat_res[i][j] = 0;
    }
  }

  while (n > 0) {
    if (n & 1) mat_res = matrix_product_mod(mat_res, mat_a, m, N);
    mat_a = matrix_product_mod(mat_a, mat_a, m, N);
    n = n >> 1;
  }

  return mat_res;
}


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

  ll N, K;
  cin >> N >> K;

  vector<vector<ll> > A(N, vector<ll>(N));
  
  for (ll i = 0; i < N; i++) {
    for (ll j = 0; j < N; j++) {
      cin >> A[i][j];
    }
  }

  vector<vector<ll> > mat_res(N, vector<ll>(N));
  mat_res = matrix_binpow_mod(A, K, MOD_M, N);

  ll ans = 0;
  
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      ans += mat_res[i][j];
      ans %= MOD_M;
    }
  }
  cout << ans << endl;
  
  return 0;
}




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

vector<int>E[100000];
int d[100000];
int main() {
	int n; scanf("%d", &n);
	rep(i, n - 1) {
		int a, b; scanf("%d%d", &a, &b); a--; b--;
		E[a].push_back(b); E[b].push_back(a);
	}
	int k; scanf("%d", &k);
	priority_queue<P, vector<P>, greater<P>>que;
	memset(d, -1, sizeof(d));
	rep(i, k) {
		int v, p; scanf("%d%d", &v, &p); v--;
		d[v] = p;
		que.push(P(p, v));
	}
	while (!que.empty()) {
		P p = que.top(); que.pop();
		for (int v : E[p.second]) {
			if (d[v] == -1) {
				d[v] = p.first + 1;
				que.push(P(d[v], v));
			}
			else if (d[v]) {
				if (abs(d[v] - p.first) != 1) {
					puts("No"); return 0;
				}
			}
		}
	}
	puts("Yes");
	rep(i, n)printf("%d\n", d[i]);
}

Measured memory_bytes: 7924
#include<bits/stdc++.h>
#define int long long
typedef long long ll;
using namespace std;
const int N=1e6;
const int P=1e9+7;
int f[N];
int inv[N];
int qpow(int a,int b){
	int res=1;
	for(;b;b>>=1){
		if(b&1){
			res=1ll*res*a%P;
		}
		a=1ll*a*a%P;
	}
	return res;
}
int C(int n,int m){
	return f[n]*qpow(f[m],P-2)%P*qpow(f[n-m],P-2)%P;
}
signed main()
{
	int n=200000,k;
	cin>>n>>k;
	f[0]=1;
	for(int i=1;i<N;i++){
		f[i]=i*f[i-1]%P;
	}
	if(k==0){
		cout<<1;
		return 0;
	}
	else if(k==1){
		cout<<n*(n-1)%P;
		return 0;
	}
	k=min(n,k);
	int ans=0;
	for(int i=0;i<=k;i++){
		ans+=C(n,i)*C(n-1,n-1-i)%P;
		ans%=P;
	}
	cout<<ans;
}

Measured memory_bytes: 9728
#include <iostream>
using namespace std;
static const int MAX=100;
static const int INFTY=(1<<21);
static const int WHITE=0;
static const int GRAY=1;
static const int BLACK=2;

int n,M[MAX][MAX];

int prim()
{
  int u,minv;
  int d[MAX],p[MAX],color[MAX];

  for(int i=0;i<n;i++)
    {
      d[i]=INFTY;
      p[i]=-1;
      color[i]=WHITE;
    }

  d[0]=0;

  while(1)
    {
      minv=INFTY;
      u=-1;
      for(int i=0;i<n;i++)
	{
	  if(minv>d[i] && color[i]!=BLACK)
	    {
	      u=i;
	      minv=d[i];
	    }
	}
      if(u==-1) break;
      color[u]=BLACK;
      for(int v=0;v<n;v++)
	{
	  if(color[v]!=BLACK && M[u][v]!=INFTY) 
	    {
	      if(d[v]>M[u][v])
		{
		  d[v]=M[u][v];
		  p[v]=u;
		  color[v]=GRAY;
		}
	    }
	}
    }
  int sum=0;
  for(int i=0;i<n;i++)
    {
      if(p[i]!=-1)sum+=M[i][p[i]];
    }

  return sum;
}

int main()
{
  cin>>n;

  for(int i=0;i<n;i++)
    {
      for(int j=0;j<n;j++)
	{
	  int e;cin>>e;
	  M[i][j]=(e==-1)?INFTY:e;
	}
    }

  cout<<prim()<<endl;

  return 0;
}



Measured memory_bytes: 3136
#include <bits/stdc++.h>
using namespace std;
int main(){
  int h, w;
  cin >> h >> w;
  vector<vector<char>> c(h, vector<char>(w));
  for(int i=0;i<h;i++){
    for (int j=0;j<w;j++){
      cin >> c[i][j];
    }
  }
  for (int i=0;i<h;i++){
    for (int j=0;j<w;j++){
      cout << c[i][j];
    }
    cout << endl;
    for (int j=0;j<w;j++){
      cout << c[i][j];
    }
    cout << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll=int_fast64_t;
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    istream& in(cin);
    ostream& out(cout);
    int n;
    ll k;
    in>>n>>k;
    vector<int> a(n),f(n);
    for(auto&i:a) in>>i;
    for(auto&i:f) in>>i;
    sort(a.begin(),a.end());
    reverse(a.begin(),a.end());
    sort(f.begin(),f.end());
    ll l=-1,r=1e18,m;
    while(r-l>1){
        m=(l+r)>>1;
        ll s=0;
        fr(i,n) if(a[i]>m/f[i]) s+=a[i]-m/f[i];
        if(s>k) l=m;
        else r=m;
    }
    cout<<r<<endl;
}

Measured memory_bytes: 1792
def countingSort(A, B, k):
    C = [0 for _ in range(k+1)]
    for i in range(n):
        C[A[i]] += 1
    for i in range(1, k):
        if i > 0:
            C[i] += C[i-1]
    for i in reversed(range(n)):
        B[C[A[i]] - 1] = A[i]
        C[A[i]] -= 1

n = int(input())
A = list(map(int, input().split(" ")))
B = [0 for _ in range(n)]
countingSort(A, B, 10000)
print(*B)


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

using namespace std;



int main()
{
    int n;
    cin >> n;
    
    int out = n % 1000;

    if (out == 0) {
        cout << 0;
    }
    else {
        cout << 1000 - out;
    }

    return 0;
}



Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#define dbg(x...) do { cout << "\033[32;1m " << #x << " -> "; err(x); } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
typedef long long ll;
typedef pair<int,int> pi;
typedef vector<int> vi;
template<class T> using vc=vector<T>;
template<class T> using vvc=vc<vc<T>>;
template<class T> void mkuni(vector<T>&v)
{
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
}
ll rand_int(ll l, ll r) //[l, r]
{
    static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
    return uniform_int_distribution<ll>(l, r)(gen);
}
template<class T>
void print(T x,int suc=1)
{
    cout<<x;
    if(suc==1) cout<<'\n';
    else cout<<' ';
}
template<class T>
void print(const vector<T>&v,int suc=1)
{
    for(int i=0;i<v.size();i++)
    print(v[i],i==(int)(v.size())-1?suc:2);
}
int main()
{
    int n,k;
    cin>>n>>k;
    ll ans=0;
    int c1=0,c2=0;
    c1=n/k;
    c2=n/(k/2)-c1;
    ans=1LL*c1*c1*c1;
    if(k%2==0) ans+=1LL*c2*c2*c2;
    print(ans);
}

Measured memory_bytes: 256
n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))

a.insert(0,0)
ans = 0
i = 1

for x in range(n+1):
    if a[i] == 2:
        ans += 1
        break
    elif x == n:
        ans = -1
        break
    else:
        ans += 1
        i = a[i]
print(ans)

Measured memory_bytes: 7084
import sys
sys.setrecursionlimit(4100000)

#Union Findデータ構造
class UnionFind:
    def __init__(self, n):
        #Data: 正:親要素のノード番号, 負:サイズ
        self.D = [-1 for i in range(n)]
    
    def find(self, x:int)->int:
        if self.D[x] < 0:
            return x
        else:
            self.D[x] = self.find(self.D[x])
            return self.D[x]

    
    def unite(self, x:int, y:int)->bool:
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        else:
            if self.D[x] > self.D[y]:
                self.D[x], self.D[y] = self.D[y], self.D[x]
            else:
                pass
            self.D[x] += self.D[y]
            self.D[y] = x
            return True

    def same(self, x:int, y:int)->bool:
        return self.find(x) == self.find(y)

    def size(self, x:int)->int:
        return -self.D[self.find(x)]

n, m, k = map(int, input().split())

uf = UnionFind(n)  

CF = [0] * n #Count Friend
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    CF[a] += 1
    CF[b] += 1
    uf.unite(a, b)

CBinG = [0] * n #Count Block in Group
for i in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if uf.same(c, d) == True:
        CBinG[c] += 1
        CBinG[d] += 1
    else:
        pass
    
for i in range(n):
    ans = uf.size(i) - 1 - CF[i] - CBinG[i]
    print(ans, end=' ')



Measured memory_bytes: 36628
#include <bits/stdc++.h>
using namespace std;
struct Fast {Fast(){std::cin.tie(0);ios::sync_with_stdio(false);}} fast;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (b) - 1; i >= (a); i--)
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i < (n); i++)
#define rrep(i, n) for(int i = (n) - 1; i >= 0; i--)
#define ALL(i) (i).begin(),(i).end()
#define RALL(i) (i).begin(),(i).end(),greater<int>()
 
#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second
 
typedef long long ll;
#define TENNINE 1000000005
#define TENFIVE 100005
#define TENFIVE2 200005
// #define int long long
const int INF = 999999999;
const int MOD = 1e9 + 7;
const double EPS = 1e9 + 7;
const double PI = acos(-1);
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
 
inline int in(){int x;std::cin>>x;return x;}
 
using lint = long long;
using pint = pair<int, int>;
using vi = vector<int>;
using vii = vector<vector<int> >;
using vl = vector<long long>;
using vp = vector<pint>;
 
template <typename T> void print(T x) { std::cout << x << '\n'; }
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
  std::fill((T*)array, (T*)(array + N), val);
}

// bool check_mm(bool mm){
//     bool flag = ( 1<= mm && mm <= 12);
//     return flag;
// }

signed main(){
    int S;
    cin>>S;
    int head, tail;
    tail = S % 100;
    head = S /100;
    bool yymm = false;
    bool mmyy = false;
    if(1<= tail && tail <= 12){
        yymm = true;
    }
    if(1<= head && head <=12){
        mmyy = true;
    }
    // print(head);
    // print(tail);
    // print(yymm);
    // print(mmyy);
    if(yymm & mmyy){
        print("AMBIGUOUS");
    }elif(yymm){
        print("YYMM");
    }elif(mmyy){
        print("MMYY");
    }else{
        print("NA");
    }
    return 0;
}


Measured memory_bytes: 3616
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, [ $t:tt ]) => {{
        let len = read_value!($next, usize);
        (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    }};

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn dfs(v: usize, par: usize, g: &[Vec<usize>], tbl: &mut [i64]) {
    for &w in &g[v] {
        if w == par { continue; }
        let val = tbl[v];
        tbl[w] += val;
        dfs(w, v, g, tbl);
    }
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input! {
        n: usize, q: usize,
        ab: [(usize1, usize1); n - 1],
        px: [(usize1, i64); q],
    }
    let mut g = vec![vec![]; n];
    for &(a, b) in &ab {
        g[a].push(b);
        g[b].push(a);
    }

    let mut tbl = vec![0; n];
    for &(p, x) in &px {
        tbl[p] += x;
    }
    dfs(0, n, &g, &mut tbl);
    for i in 0..n {
        puts!("{} ", tbl[i]);
    }
    puts!("\n");
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


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

a.sort()

if a[0]<=0 and a[-1]>=0:
    m = 0
    for i in range(n):
        m+=abs(a[i])
elif a[0]>0:
    m = sum(a)-a[0]*2
else:
    m = a[-1]
    for i in range(n-1):
        m+=abs(a[i])

print(m)

b = [a[0]] # -
c = [] # +

for i in range(1,n-1):
    if a[i]<0:
        b.append(a[i])
    else:
        c.append(a[i])

for x in c:
    print(b[-1],end=' ')
    print(x)
    b[-1]-=x
for y in b:
    print(a[-1],end=' ')
    print(y)
    a[-1]-=y



Measured memory_bytes: 67596
K, N  = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

sorted_distance = sorted(A)
dists = []
for i in range(N - 1):
    dists.append(sorted_distance[i + 1] - sorted_distance[i])
dists.append(K + sorted_distance[0] - sorted_distance[-1])
max_dist = max(dists)
max_dist_id = dists.index(max_dist)

if max_dist_id == len(dists) - 1:
    total_dist = sum(dists[:-1])
else:
    total_dist = sum(dists[max_dist_id+ 1:]) + sum(dists[:max_dist_id])

print(total_dist)

Measured memory_bytes: 26444
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()

a = [INT() for _ in range(N)]
tmp = [0]*(N+1)
tmp2 = a[0]
cnt = 0
while 1:
	if tmp[tmp2] == 1:
		print(-1)
		break
	elif tmp2 == 2:
		print(cnt+1)
		break
	tmp[tmp2] = 1
	tmp2 = a[tmp2-1]
	cnt += 1

Measured memory_bytes: 9956
n,m=map(int,input().split())
s=input()

ans=[]
s=s[::-1]

now=0
while now<n:
    for i in range(m,0,-1):
        if now+i<=n and s[now+i]=="0":
            ans.append(i)
            now=now+i
            break
    else:
        print(-1)
        break
else:
    ans=[str(i) for i in ans]
    print(" ".join(ans[::-1]))


Measured memory_bytes: 85148
#include <stdio.h>

int solve(int,int);

int A[2000];
int n;

int main(){

  int m_i[2000];
  int i,j,q;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&m_i[i]);
  }

  for(i=0;i<q;i++){
    j=0;
    if(solve(j,m_i[i]) == 1){
      printf("yes\n");
    }
    else if(solve(j,m_i[i]) == 0){
      printf("no\n");
    }
  }
  return 0;
}

int solve(int i, int m_i){

  int res;

  if(m_i == 0){
    return 1;
  }
  if(i >= n){
    return 0;
  }
  res = solve(i+1,m_i) || solve(i+1,m_i-A[i]);

  return res;
}

Measured memory_bytes: 588
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner as = new Scanner(System.in);
		int n = Integer.parseInt(as.next());
		HashMap<String, String> hashmap = new HashMap<String, String>();
		String[] a;
		a = new String[n];
		for(int i=0;i<n;i++){
			a[i] = as.next();
			if(hashmap.get(a[i])==null){
				hashmap.put(a[i], "1");
			}else{
				int k = Integer.parseInt(hashmap.get(a[i]));
				k++;
				hashmap.put(a[i], String.valueOf(k));
			}
		}
		Collection<String> values = hashmap.values();
        Iterator<String> iteratorForValues = values.iterator();
        long kotae = 0;
        while(iteratorForValues.hasNext()) {
            long value = Long.parseLong(iteratorForValues.next());
           // System.out.println(value);
            kotae += value*(value-1)/2;
        }
        //System.out.println(kotae);
        for(int i=0;i<n;i++){
			int t = Integer.parseInt(hashmap.get(a[i]));
			//System.out.println("t="+t);
			System.out.println(kotae-2*(t-1)/2);
		}
	}
}

Measured memory_bytes: 96052
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner scn = new Scanner(System.in);
		ArrayList<Integer> caca = new ArrayList<Integer>();
		int suma = 0;
		for(int i = scn.nextInt();i>0;i--) {
			int n1 = scn.nextInt();
			caca.add(n1);
		}
		long tot = 0;
		long min = Long.MAX_VALUE;
		for(int i2 = -100;i2<=100;i2++) {
			for(int i = 0;i<caca.size();i++) {
				tot+=Math.pow(i2-caca.get(i), 2);
				if(tot>min) {
					break;
				}
			}
			if(tot<min)min = tot;
			tot = 0;
		}
		System.out.println(min);
		scn.close();
	}
}

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

#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair

using namespace std;

const LL MOD=1e9+7;

int k,a,b;

int main()
{
	cin>>k>>a>>b;
	if(a%k==0||b%k==0||a/k!=b/k) puts("OK");
	else puts("NG");
	return 0;
}

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = br.readLine();
		
		String changeLine = "";
		for(int i = 0;i<line.length();i++){
			if(Character.isUpperCase(line.charAt(i))){
				changeLine += String.valueOf(Character.toLowerCase(line.charAt(i)));
			}
			else if(Character.isLowerCase(line.charAt(i))){
				changeLine += String.valueOf(Character.toUpperCase(line.charAt(i)));
			}
			else{
				changeLine += String.valueOf(line.charAt(i));
			}
		}
		
		System.out.println(changeLine);
	}

}

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

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<long long> nal(n + 1, 0);
    map<pair<int, string>, int> mmap;

    int num_solved = 0;
    for (int i = 0; i < m; i++)
    {
        int p;
        string str;
        cin >> p >> str;
        //cout << p << " " << str << endl;
        string tmp = "AC";
        string tmp2 = "WA";
        if (str == tmp2)
        {

            //cout << "here \n";
            if (mmap.find({p, tmp}) == mmap.end())
            {
                nal[p]++;
            }
        }
        else
        {
            if (mmap.find({p, tmp}) == mmap.end())
            {
                num_solved++;
            }
        }
        mmap[{p, str}] = 1;

        //cout << " gg " << nal[p] << endl;
    }
    long long tot_penal = 0;
    //cout << "bef " << endl;
    for (int i = 1; i <= n; i++)
    {

        if (mmap.find({i, "AC"}) != mmap.end())
            tot_penal += nal[i];
    }
    cout << num_solved << " " << tot_penal << "\n";
    return 0;
}

Measured memory_bytes: 11904
/*
    @uthor: Amit Kumar
    user -->GitHub: drviruses ; CodeChef: dr_virus_ ; Codeforces,AtCoder,Hackerearth,Hakerrank: dr_virus;
*/
#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using namespace std::chrono;
//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;
//#define ln mp::cpp_int;
#define ll    long long
#define ld    long double
#define ull   unsigned long long
#define endl "\n"
ll google_itr = 1;
#define google(x) cout<<"Case #"<<x<<":"
#define pi 3.14159265358979323846264338327950L

const ll mod = 1e9+7;
const ll inf = 1e18;

ll popcount(ll num){
    num = num - ((num >> 1) & 0x55555555);
    num = (num & 0x33333333) + ((num >> 2) & 0x33333333);
    return ((num + (num >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

vector<pair<ll,ll>> factor_arr;

void myfactor(ll num){ 
    ll count = 0;   
    while (!(num % 2)) { 
        num >>= 1; count++; 
    }  
    if (count) factor_arr.push_back({2,count}); 
    for (auto i = 3; i <= sqrt(num); i += 2) { 
        count = 0; 
        while (num % i == 0) { 
            count++; 
            num /= i; 
        } 
        if (count) factor_arr.push_back({i,count}); 
    } 
    if (num > 2) factor_arr.push_back({num,1});
}

void virus(){
          ll len,k;
          cin>>len>>k;
          vector<ll> arr(len), dp(len,mod);
          for(auto &i:arr) cin>>i;
          dp[0] = 0;
          for(auto i=1; i<len; i++){
              ll str = i - k , minm = LLONG_MAX;
              if(str < 0) str = 0;
              for(auto j=str; j<=i; j++){
                  ll val = dp[j] + abs(arr[j] - arr[i]);
                  if(minm > val) minm = val;
              }
              dp[i] = minm;
          }
          cout<<dp[len-1]<<endl;
}


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
  /*#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif*/

    ll t = 1;
    //cin>>t;
    while(t--){
           auto start = high_resolution_clock::now();
           virus();
           auto stop = high_resolution_clock::now();
           auto duration = duration_cast<seconds>(stop - start);
         //cout << "Time: "<<duration.count()<<endl;
        //your code goes here
    }
    return 0;
}

Measured memory_bytes: 4796
import javax.swing.*;
import java.util.*;



/**
 * Created by santa on 2016/10/16.
 */

public class Main {


    static class pair {
            public int a;
            public int b;

            pair(){
                this.a = 0;
                this.b = 0;
            }

            pair(int a, int b){
                this.a = a;
                this.b = b;
            }

            public void set(int a, int b) {
                this.a = a;
                this.b = b;
            }
        }

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

        int N = scanner.nextInt();


        int[] a = new int[N];

        for (int i = 0; i < N; i++) {
            a[i] = scanner.nextInt() - 1;
        }

        int[] list = new int[N];
        int next = 0;
        int c = 1;
        int flag = 0;
        while(true){
            if(a[next] == 1){
                flag = c;
                break;
            }
            next = a[next];
            if(list[next] == 1){
                flag = -1;
                break;
            }
            list[next] = 1;
            c++;
        }

        System.out.println(flag);



    }




} // MainClass


Measured memory_bytes: 50588
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())

class UnionFind:
    def __init__(self, numV):
        self.pars = list(range(numV))
        self.ranks = [0] * numV
    def getRoot(self, x):
        par = self.pars[x]
        if par != x:
            self.pars[x] = par = self.getRoot(par)
        return par
    def merge(self, x, y):
        x, y = self.getRoot(x), self.getRoot(y)
        if x == y: return
        if self.ranks[x] < self.ranks[y]:
            self.pars[x] = y
        else:
            self.pars[y] = x
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x] += 1
    def isSame(self, x, y):
        return self.getRoot(x) == self.getRoot(y)
    def updatePars(self):
        for v in range(len(self.pars)):
            self.getRoot(v)

UF = UnionFind(N)

anss = []
for _ in range(Q):
    t, u, v = map(int, input().split())
    if t == 0:
        UF.merge(u, v)
    else:
        anss.append(int(UF.isSame(u, v)))

print('\n'.join(map(str, anss)))


Measured memory_bytes: 22192
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(void){
    string s;
    int b=0;
    
    while(cin>>s){
        int c=0;
        int a=s.size();
       /* string s2 = s;
        if(a%2==0){
            int b=a/2;
            reverse(s.begin()+b,s.end());
            if() c++;
        }*/
        for(int i=0;i<a/2;i++){
            if(*(s.begin()+i)!=*(s.end()-i-1)) c--;
        }
        if(c==0) b++; 
    }
       cout<<b<<endl;
       
    return 0;
}



Measured memory_bytes: 3004
import java.util.Scanner;

public class Main{
    public static void main(String[]argc){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        if(a<b){
            System.out.println("a < b");
        }else if(a>b){
            System.out.println("a > b");
        }else{
            System.out.println("a == b");
        }
    }
}




Measured memory_bytes: 26168
N, M, C = map(int, input().split())

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

cnt = 0

for i in range(N):
    A = list(map(int, input().split()))
    sum_value = [x*y for x, y in zip(A, B)]
    if (sum(sum_value)+C)>0:
        cnt += 1

print(cnt)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+10,mod=1e9+7;
int c[maxn],w[maxn],Mi[maxn][3],mi[maxn][3],f[maxn],f1[maxn],sum[maxn];
int hea[maxn],to[maxn<<3],nxt[maxn<<3],cnt,ans=1,tot;
void add(int a,int b) {
	nxt[++tot]=hea[a];
	hea[a]=tot;
	to[tot]=b;
}
int qpow(int a,int b) {
	int ans=1;
	while(b) {
		if(b&1)ans=1ll*ans*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return ans;
}
void dfs(int x) {
	f[x]=1;
	ans=1ll*ans*++cnt%mod;
	ans=1ll*ans*qpow(++sum[c[x]],mod-2)%mod;
	for(int i=hea[x];i;i=nxt[i])
		if(!f[to[i]])dfs(to[i]);
}
void dfs1(int x) {
	f1[x]=1;
	sum[c[x]]=0;
	for(int i=hea[x];i;i=nxt[i])
		if(!f1[to[i]])dfs1(to[i]);
}
signed main() {
	memset(Mi,0x3f,sizeof(Mi));
	int n,x,y;
	scanf("%lld%lld%lld",&n,&x,&y);
	for(int i=1;i<=n;i++) {
		scanf("%lld%lld",c+i,w+i);
		if(w[i]<Mi[c[i]][0]) {
			Mi[c[i]][0]=w[i];
			mi[c[i]][0]=i;
		}
		if(w[i]<Mi[c[i]-1][1]) {
			Mi[c[i]-1][1]=w[i];
			mi[c[i]-1][1]=i;
		}
		if(w[i]<Mi[c[i]+1][2]) {
			Mi[c[i]+1][2]=w[i];
			mi[c[i]+1][2]=i;
		}
	}
	for(int i=n;i>=1;i--)
		if(Mi[i+1][1]<Mi[i][1]) {
			Mi[i][1]=Mi[i+1][1];
			mi[i][1]=mi[i+1][1];
		}
	for(int i=1;i<=n;i++)
		if(Mi[i-1][2]<Mi[i][2]) {
			Mi[i][2]=Mi[i-1][2];
			mi[i][2]=mi[i-1][2];
		}
	for(int i=1;i<=n;i++) {
		if(Mi[c[i]][0]+w[i]<=x) {
			add(i,mi[c[i]][0]);
			add(mi[c[i]][0],i);
		}
		if(Mi[c[i]][1]+w[i]<=y) {
			add(i,mi[c[i]][1]);
			add(mi[c[i]][1],i);
		}
		if(Mi[c[i]][2]+w[i]<=y) {
			add(i,mi[c[i]][2]);
			add(mi[c[i]][2],i);
		}
	}
	for(int i=1;i<=n;i++)
		if(!f[i]) {
			cnt=0;
			dfs(i);
			dfs1(i);
		}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 38392
#include <algorithm>
#include <iostream>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;

int main(void) {
  int N, M, R;
  cin >> N >> M >> R;
  vector<int> city(R);
  rep(i, R) {
    cin >> city[i];
    --city[i];
  }
  sort(city.begin(), city.end());

  const int INF = 100000000;
  vector<vector<int>> G(N, vector<int>(N, INF));
  rep(i, M) {
    int a, b, c;
    cin >> a >> b >> c;
    --a;
    --b;
    G[a][b] = c;
    G[b][a] = c;
  }

  rep(k, N) {
    rep(i, N) {
      rep(j, N) {
        if (G[i][k] == INF || G[k][j] == INF) continue;
        G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
      }
    }
  }

  int answer = INF;
  do {
    int dist = 0;
    rep(i, R - 1) { dist += G[city[i]][city[i + 1]]; }
    answer = min(answer, dist);
  } while (next_permutation(city.begin(), city.end()));
  cout << answer << endl;
  return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n ; i++)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x) // decltypeで型取得、引数があればva_argsのところに入れる
using namespace std;
typedef long long ll; // long longをllでかけるようにした
const int INF = 1e9;
const double PI = 3.1415926535;
const int MOD = 1000000007; // 計算してからmodで割る ans = (ans * a) % mod
#define int long long
template <typename T = long long > T in () { T x; cin >> x; return(x);}
// int a = in() のように使うlong long以外の型の時はstirng s = in<string>()のように型を指定する

signed main(void){
    int n, k; cin >> n >> k;
    if(n > 10) cout << k << endl;
    else cout << k + (100 * (10 - n)) << endl;
}

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

int main() {
    int n, x, y;
    cin >> n >> x >> y;
    x--; y--;

    vector<int> ans(n,0);
    rep(i,n){
        for(int j = i+1; j < n; j++){
            int dij;
            if(i <= x){
                if(j <= x){
                    dij = j-i;
                }
                else if(j < y){
                    dij = min(j-i,x-i+1+y-j);
                }
                else{
                    dij = x-i+1+j-y;
                }
            }
            else if(i < y){
                if(j < y){
                    dij = min(j-i,i-x+1+y-j);
                }
                else{
                    dij = min(j-i,i-x+1+j-y);
                }
            }
            else{
                dij = j-i;
            }

            ans[dij]++;
        }
    }

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


Measured memory_bytes: 256
x, n = map(int, input().split())
p = [int(i) for i in input().split()]

cand = []
for i in range(102):
    if i in p:
        continue
    else:
        cand.append(abs(i-x))
q = min(cand)
print(x-q if x-q not in p else x+q)

Measured memory_bytes: 61912
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef __int128_t LL;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define F first
#define S second
#define pb push_back
mt19937 rnd;

#define div divi

const int mod = 1e9 + 7;

inline int add(int a, int b) {
    if (a + b >= mod) return a + b - mod;
    else return a + b;
}

inline int sub(int a, int b) {
    if (a - b < 0) return a - b + mod;
    else return a - b;
}

inline int mult(int a, int b) {
    return 1ll * a * b % mod;
}

inline int binpow(int a, int n) {
    int res = 1;
    while (n) {
        if (n & 1) {
            res = mult(res, a);
        }
        a = mult(a, a);
        n >>= 1;
    }
    return res;
}

inline int inv(int a) {
    return binpow(a, mod - 2);
}

inline int div(int a, int b) {
    return mult(a, inv(b));
}

const int N = 2e5 + 10;
int f[N];
int f_inv[N];

inline int C(int n, int k) {
    if (n < k) return 0;
    return mult(f[n], mult(f_inv[k], f_inv[n-k]));
}

void init() {
    f[0] = 1;
    for (int i = 1; i <= N - 1; i++) {
        f[i] = mult(f[i - 1], i);
    }
    f_inv[N - 1] = inv(f[N - 1]);
    for (int i = N - 2; i >= 0; i--) {
        f_inv[i] = mult(f_inv[i + 1], i + 1);
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    init();
    int h, w, a, b;
    cin >> h >> w >> a >> b;
    int ans = 0;
    for (int i = h - a + b; i <= h + w - 2 && h + w - 2 - i >= a - 1; i++) {
        ans = add(ans, mult(C(i - 1, h - a - 1), C(h + w - 2 - i, a - 1)));
    }
    cout << ans << "\n";

#ifdef LOCAL
    cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}


Measured memory_bytes: 5232
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <list>
#include <deque>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
#define dump(a) cout << (a) << endl;
typedef long long ll;
ll mod = 1e9+7;
ll MOD = 998244353;

map<int, int> mp;

int f(int a, int b, int c) {
    int res = 0;
    for (auto itr = mp.begin(); itr != mp.end(); itr++) {
        auto tmp = itr;
        tmp++;
        for (auto itr2 = tmp; itr2 != mp.end(); itr2++) {
            tmp = itr2;
            tmp++;
            for (auto itr3 = tmp; itr3 != mp.end(); itr3++) {
                if (itr->second >= a && itr2->second >= b && itr3->second >= c) {
                    res++;
                }
            }
        }
    }
    return res;
}

int g(int a, int b) {
    int res = 0;
    for (auto itr = mp.begin(); itr != mp.end(); itr++) {
        auto tmp = itr;
        tmp++;
        for (auto itr2 = tmp; itr2 != mp.end(); itr2++) {
           if (itr->second >= a && itr2->second >= b) {
               res++;
           }
        }
    }
    return res;
}

int h(int a) {
    int res = 0;
    for (auto itr = mp.begin(); itr != mp.end(); itr++) {
        if (itr->second >= a) res++;
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    int cnt = 0;
    for (int j = 2; j <= n; j++) {
        int k = j;
        int i = 2;
        while (k != 1) {
            while (k != 0 && k%i == 0) {
                k /= i;
                mp[i]++;
            }
            i++;
        }
    }
    //puts("a");
    cnt += f(2, 4, 4);
    cnt += f(4, 2, 4);
    cnt += f(4, 4, 2);
    cnt += g(4, 14);
    cnt += g(14, 4);
    cnt += g(2, 24);
    cnt += g(24, 2);
    cnt += h(74);
    dump(cnt);
    return 0;  
}

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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

template<class T> inline T sqr(T x) {return x*x;}

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())

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

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const long long INF = 1000000007;

#define CLR(a) memset((a), 0 ,sizeof(a))

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main(void){
    int N,A; cin >> N >> A;
    cout << (N-N/500*500 > A ? "No" : "Yes") << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    long long n;
    cin >>n;
    string x;
    long c0=0,c1=0,c2=0,c3=0;
    while(n>0)
    {
        cin>>x;
        if(x=="AC")
        {
            c0++;
        }
        else if (x=="WA"){
            c1++;
    }
        else if (x=="TLE"){
            c2++;
    }
        else if (x=="RE"){
            c3++;
            }
            n--;
    }
    cout<<"AC x "<<c0<<"\n"<<"WA x "<<c1<<"\n"<<"TLE x "<<c2<<"\n"<<"RE x "<<c3;
    return 0;
}


Measured memory_bytes: 3620
# D
N = int(input())
s = list(map(int, list(input())))

        
def calc_add(temp_list):
    if len(temp_list) <= 1:
        return 0
    else:
        res = 0
        # use 101 for left
        dp_l = [0]*len(temp_list)
        # use 101 for right 
        dp_r = [0]*len(temp_list)
        # do not use 101
        dp_c = [0]*len(temp_list)
        for i in range(len(temp_list) - 1):
            if temp_list[i] > 1:
                dp_l[i+1] = max(dp_l[i] + temp_list[i] - 1, dp_c[i] + temp_list[i])
            else:
                dp_l[i+1] = dp_c[i] + temp_list[i]
            if temp_list[i] > 1:
                dp_r[i+1] = max(dp_l[i] + temp_list[i+1], dp_c[i] + temp_list[i+1], dp_r[i] + temp_list[i+1] - 1)
            else:
                dp_r[i+1] = dp_c[i] + temp_list[i+1]
            dp_c[i+1] = max(dp_l[i], dp_r[i], dp_c[i])
        
        return max(dp_l[-1], dp_r[-1], dp_c[-1])
    

cont0 = 1
cont00 = 1
temp_list = []
res = 0

for i in range(N):
    if s[i] == 1:
        if cont0 == 1:
            temp_list.append(1)
            cont0 = 0
            cont00 = 0
        else:
            temp_list[-1] += 1
    else:
        if cont00 == 1:
            pass
        elif cont0 == 1:
            cont00 = 1
            res += calc_add(temp_list)
            temp_list = []
        else:
            cont0 = 1
            
    if i == N - 1:
        res += calc_add(temp_list)
        
print(res)

Measured memory_bytes: 12200
import collections

N ,M = map(lambda x: int(x),input().split())

A = list(map(lambda x: int(x),input().split()))

A_dict = collections.Counter(A)

for i in range(M):
    B,C = map(lambda x: int(x),input().split())
    if C in A_dict.keys():
        A_dict[C] += B
    else:
        A_dict[C] = B

A_dict_sorted = sorted(A_dict.items(), key=lambda x:-x[0])

total = 0
length = 0
for k,v in A_dict_sorted:
    if N>length+v:
        length += v
        total += k*v
    else:
        total += (N-length)*k
        break
#print(A_dict_sorted)
print(total)


Measured memory_bytes: 49696
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))

N=intput()
A=lint()
B=lint()
k=sum(B)-sum(A)
opa=opb=0
for a,b in zip(A,B):
    opa+=max(0,(b-a+1)//2)
    opb+=max(0,a-b)
judge(opa<=k and opb<=k)

Measured memory_bytes: 74684
#include <bits/stdc++.h>
#define repp(i,l,r)for(long long i=(l);i<(r);i++)
#define rep(i,n) for (long long i = 0; i < (n); ++i)
#define per(i,n) for (long long i = (n); i >= 0; --i)
const int INF = 2147483647;//int max
const long long int MOD = 1000000007;
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//ミョ(-ω- ?)
int main() {
    ll a,v,b,w,t;
    cin >> a >> v >> b >> w >> t;
    if(w > v){
        cout << "NO\n";
        return 0;
    }
    if(abs(a-b) <= abs(w-v)*t){
        cout << "YES\n";
    }else{
        cout << "NO\n";
    }
    return 0;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b!=0?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}

int main(){
    ll n;
    cin>>n;
    vector<ll> a(n),c(n,0);
    rep(i,n){
        cin>>a[i];
        a[i]--;
        c[a[i]]++;
    }
    ll allc=0;
    rep(i,n){
        allc+=c[i]*(c[i]-1)/2;
    }
    rep(i,n){
        cout<<allc-(c[a[i]]-1)<<endl;
    }
    return 0;
}

Measured memory_bytes: 5760
N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

# print(N // (K - 1))
if (N - 1) % (K - 1) == 0:
    print((N - 1) // (K - 1))
else:
    print((N - 1) // (K - 1) + 1)


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

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;A++)
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////
int N,K;
char S[101010];
int i, j,k,ans;
int main(){
    scanf("%d%d%s",&N,&K ,S);
    int l=0, r=0,c=S[0]=='0';
    while(true){
        while(r+1<N){
            if(S[r]=='1'&&S[r+1]!='1'){
                c++;
                if(c>K)
                    break;
            }
            r++;
        }
        ll a = r + 1 - l;
        if(a>ans){
            ans = a;
        }
        if(r+1==N)
            break;
        r++;
        while(true){
            if(S[l]=='0'&&S[l+1]!='0'){
                break;
            }
            l++;
        }
        l++;
    }
    printf("%d", ans);
    return 0;
}

Measured memory_bytes: 384
import java.util.Scanner;

public class Main {
    public static void main(String... args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int a[] = new int[n];
        for(int i = 0;i < n;i++)a[i] = scan.nextInt();

        boolean f = true;
        int t = 0;
        while(f){
            f = false;
            for(int i = n-1;i >= 1;i--){
                if(a[i] < a[i-1]){
                    int c = a[i];
                    a[i] = a[i-1];
                    a[i-1] = c;
                    f = true;
                    t++;
                }
            }
        }
        for(int i = 0;i < n;i++){
            if(i != 0)System.out.print(" ");
            System.out.print(a[i]);
        }
        System.out.println();
        System.out.println(t);

        scan.close();
    }

}


Measured memory_bytes: 26260
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <functional>
#include <queue>
#include <unordered_set>
#include <climits>
#include <set>

using namespace std;
typedef long long ll;

int main()
{
	ll N;
	ll A[100001];
	A[0] = 0;
	cin >> N;
	for(int i = 1; i <= N; i++){
		cin >> A[i];
	}
	
	ll ans = 0;
	for(int i =1; i <= N; i++){
		if(A[i-1] == 1){
			if(A[i] > 0){
				ans++;
				A[i]--;
			}
		}
		ans += A[i]/2;
		A[i] -= (A[i]/2)*2;
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 1024
N,K = map(int,input().split())
S = input()

l = 0
count = 0

ans = 0
for r in range(N):
    if S[r] == '0':
        if r==0 or S[r-1]=='1':
            count += 1
    if count > K:
        while S[l] == '1':
            l += 1
        while S[l] == '0':
            l += 1
        count -= 1
    ans = max(ans, r-l+1)

print(ans)


Measured memory_bytes: 42096