akhauriyash/Code-Regression huggingface dataset:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def div_cnt(n):
    res = 0
    while(n):
        n/=2
        res += 1
    return res
def ok(D):
    for i,d in enumerate(D):
        if(div_cnt(d) > i+1):
            return False
    return True
def main():
    N=I()
    D=LI()
    D_rev = D[::-1]
    up = 10**18
    B = [1]*(N+1) #その深さに存在出来る点の数
    for i in range(N):
        B[i + 1] = min(up, (B[i]-D[i]) * 2) 
    # print(B)
    B_rev = B[::-1]

    ans = 0
    now = 0
    for i,a in enumerate(D_rev):
        if(a>B_rev[i]):
            print(-1)
            return 
        now += a
        now = min(now, B_rev[i])
        ans += now
    print(ans)
if __name__ == '__main__':
    main()

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

int main (){
    string S;
    cin >> S;
    int count = 0;
    bool flag = false;
    for (char c = 'a'; c <= 'z'; c++)
    {
        count = 0;
        for (int i = 0; i < S.size();i++)
        {
            if (c != S[i])
            {
                count++;
            }
        }
        if(count == S.size()){
            cout << c << endl;
        
            flag = true;
            break;
        }
    }
    if(flag == false){
        cout << "None" << endl;
    }
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define ll long long int
#define mp make_pair
#define pb push_back
#define si(x) scanf("%d",&x)
#define pi(x) printf("%d\n",x)
#define s(x) scanf("%I64d",&x)
#define p(x) printf("%I64d\n",x)
#define sc(x) scanf("%s",x)
#define pc(x) printf("%s",x)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define F first
#define S second
#define M 1000000007
#define N 1000002
#define inf 1e15
#define PQG priority_queue< int,std::vector<int>,std::greater<int> >
#define PQL priority_queue< int,std::vector<int>,std::less<int> >
#define PQPL priority_queue<pii ,vector< pii >, less< pii > >
#define PQPG priority_queue<pii ,vector< pii >, greater< pii > >
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)

using namespace std;


int main() {
    fast_io;
    int n;
    ll k;
    cin>>n>>k;
    ll a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    ll ans=0;
    for(int i=1;i<n;i++){
        ans+=min(a[i]-a[i-1],k);
    }
    cout<<ans+k<<endl;

    return 0;
}


Measured memory_bytes: 1920
// g++ -std=c++11 temp.cpp
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;

#define INF INT_MAX/3

#define MAX_N 1000

string sa,sb,sc;
int a,b,c;
int state;

int main(){
	cin.sync_with_stdio(false);
	cin>>sa>>sb>>sc;
	while(1){
		if(state==0){
			if(a==sa.length())break;
			state=sa[a++]-'a';
		}else if(state==1){
			if(b==sb.length())break;
			state=sb[b++]-'a';
		}else{
			if(c==sc.length())break;
			state=sc[c++]-'a';
		}
	}
	cout<<(char)('A'+state)<<endl;
	return 0;
}





Measured memory_bytes: 256
import java.io.PrintWriter


private data class City(var index: Int = 0, var prov: Int = 0, var year: Int = 0, var label: String = "")

fun main(args: Array<String>) {
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }

    val d = Array(n) { mutableListOf<City>() }
    for (i in 0 until m) {
        val (p, y) = readLine()!!.split(" ").map { it.toInt() }
        d[p - 1].add(City(index = i, year = y))
    }

    for ( i in 0 until n) {
        d[i].sortBy{ it.year }
        for ( j in 0 until d[i].size) {
            d[i][j].label = "%06d%06d".format(i+1, j+1)
        }
    }

    val ans = d.toMutableList().flatten().sortedBy { it.index }


    val out = PrintWriter(System.out)
    out.println(ans.map { it.label }.joinToString("\n"))
    out.flush()
}

Measured memory_bytes: 146312
#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#define endl "\n"
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    if(n == m)
    	cout << "Yes" << endl;
    else
    	cout << "No" << endl; 
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int i,j,status=0,n1,n2,n;
    string s,t,f1,f2;
    cin>>s>>t;
    n=s.length();
   /* n1=s.length();
    n2=t.length();
    if(n1!=n2)
    {
        cout<<"No";
        return 0;
    }
    for(i=0;i<n;i++)
    {
        if(islower(s[i])&&islower(t[i]))
        {
            status==0
        }
        else
        {
            cout<<"No";
            return 0;
        }
    }*/
    /*for(i=0;i<n;i++)
    {
        f1[s[i]-97]++;
        f2[t[i]-97]++;
    }
    for(i=0;i<25;i++)
    {
        if(f1[i]!=f2[i])
        {
            cout<<1;
            cout<<"No";
            return 0;
        }
    }*/
    f1=s;
    f2=t;
    sort(f1.begin(),f1.end());
    sort(f2.begin(),f2.end());
    if(f1.compare(f2)!=0)
    {
      //  cout<<1;
        cout<<"No";
        return 0;
    }
    for(i=0;i<n;i++)
    {
    //    cout<<3;
        if(s.compare(t)==0)
        {
            cout<<"Yes";
            return 0;
        }
        else
        {
            //cout<<4;
            char a=s[n-1];
            for(j=0;j<n-1;j++)
            {
              //  cout<<5;
                s[n-1-j]=s[n-2-j];
            }
            s[0]=a;
        }
    }
    if(s.compare(t)!=0)
    {
        //cout<<2;
        cout<<"No";
    }
    return 0;
}


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

using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define MIN(a, b) ((a) > (b) ? (b) : (a))
#define MAX(a, b) ((a) < (b) ? (b) : (a))

const long long INF = 1LL << 60;
typedef long long ll;
const long long MOD = 1000000000 + 7;

int main()
{
    ll n, a, b, c, d, e;
    cin >> n >> a >> b >> c >> d >> e;
    ll min_transe;
    min_transe = MIN(a, b);
    min_transe = MIN(min_transe, c);
    min_transe = MIN(min_transe, d);
    min_transe = MIN(min_transe, e);
    cout << 4 + (n + (min_transe - 1)) / min_transe << endl;
    return 0;
}

Measured memory_bytes: 3632
#include<iostream>
#include<algorithm>
#include<set>
#include<cstring>
typedef long long ll; 
using namespace std;
int main()
{
	int n, a[110], sum = 0;
	cin>>n;
	for(int i = 0; i < n; i++){
		cin>>a[i];
	}
	for(int i = 0; i < n - 1; i++){
		for(int j = i + 1; j < n; j++){
			sum += a[i] * a[j];
		}
	}
	cout<<sum<<endl;
}

Measured memory_bytes: 256
//package com.company;
import java.util.*;
import java.lang.*;
import java.io.*;
//****Use Integer Wrapper Class for Arrays.sort()****
public class Main {
    static PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[] Args)throws Exception{
        FastReader scan=new FastReader(System.in);
        int t=1;
//        t=scan.nextInt();
        while(t-->0){
            int n=scan.nextInt();
            String s=scan.next();
            int rc=0;
            for(int i=0;i<n;i++){
                if(s.charAt(i)=='R'){
                    rc++;
                }
            }
            int c=rc;
            for(int i=0;i<n;i++){
                if(s.charAt(i)=='R'&&i<c){
                    rc--;
                }
            }
            out.println(rc);
        }
        out.flush();
        out.close();
    }
    static class FastReader {

        byte[] buf = new byte[2048];
        int index, total;
        InputStream in;

        FastReader(InputStream is) {
            in = is;
        }

        int scan() throws IOException {
            if (index >= total) {
                index = 0;
                total = in.read(buf);
                if (total <= 0) {
                    return -1;
                }
            }
            return buf[index++];
        }

        String next() throws IOException {
            int c;
            for (c = scan(); c <= 32; c = scan()) ;
            StringBuilder sb = new StringBuilder();
            for (; c > 32; c = scan()) {
                sb.append((char) c);
            }
            return sb.toString();
        }

        int nextInt() throws IOException {
            int c, val = 0;
            for (c = scan(); c <= 32; c = scan()) ;
            boolean neg = c == '-';
            if (c == '-' || c == '+') {
                c = scan();
            }
            for (; c >= '0' && c <= '9'; c = scan()) {
                val = (val << 3) + (val << 1) + (c & 15);
            }
            return neg ? -val : val;
        }
        long nextLong() throws IOException {
            int c;
            long val = 0;
            for (c = scan(); c <= 32; c = scan()) ;
            boolean neg = c == '-';
            if (c == '-' || c == '+') {
                c = scan();
            }
            for (; c >= '0' && c <= '9'; c = scan()) {
                val = (val << 3) + (val << 1) + (c & 15);
            }
            return neg ? -val : val;
        }
    }
}


Measured memory_bytes: 33728
package main

import "fmt"

func bitCount(bit int) int {
	cnt := 0
	for i := 0; i < 64; i++ {
		if bit&(1<<uint(i)) != 0 {
			cnt++
		}
	}
	return cnt
}

func main() {
	var N int
	fmt.Scan(&N)
	m := make(map[byte]int, 0)
	for i := 0; i < N; i++ {
		var s string
		fmt.Scan(&s)
		if s[0] == 'M' || s[0] == 'A' || s[0] == 'R' || s[0] == 'C' || s[0] == 'H' {
			m[s[0]]++
		}
	}
	keys := make([]byte, 0)
	for k := range m {
		keys = append(keys, k)
	}
	ans := 0
	if len(keys) >= 3 {
		for bit := 0; bit < (1 << uint(len(m))); bit++ {
			if bitCount(bit) == 3 {
				cnt := 1
				for j := 0; j < len(m); j++ {
					if (bit & (1 << (uint(j)))) != 0 {
						cnt *= m[keys[j]]
					}
				}
				ans += cnt
			}
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 5504
# -*- coding: utf-8 -*-
"""
Created on Tue Oct 15 08:23:21 2019

@author: avina
"""

n = int(input())
l = list(map(int, input().split()))

even_sum = 0
odd_sum = 0
for i in range(n):
    if i%2 ==0:
        even_sum+=l[i]
    else:
        odd_sum += l[i]
j = 0
for i in range(n):
    print(abs(even_sum - odd_sum), end = ' ')
    
    odd_sum, even_sum= even_sum - l[j],odd_sum + l[j]
    j += 1

Measured memory_bytes: 14092
def left(i:int):
    return i * 2

def right(i:int):
    return i * 2 + 1

def maxHeapify(A:list, i:int):
    l = left(i)
    r = right(i)
    global H
    if l <= H  and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r <= H  and A[r] > A[largest]:
        largest = r
    if largest != i:
        A[i],A[largest] = A[largest],A[i]
        maxHeapify(A, largest)

def buildMaxHeap(A:list):
    global H
    for i in range(int(H/2), 0, -1):
        maxHeapify(A, i)

H = int(input())
A = [None]
A.extend(list(map(int,input().split())))
buildMaxHeap(A)
print(" ", end="")
print(*A[1:])


Measured memory_bytes: 63700
#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}
#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}
#[allow(dead_code)]
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
#[allow(dead_code)]
fn yn(result: bool) {
    if result {
        println!("Yes");
    } else {
        println!("No");
    }
}

use std::collections::BinaryHeap;
fn main() {
    let v = read_vec::<u32>();
    let n = v[0] as usize;
    let m = v[1];
    let a = read_vec::<u64>();
    let mut heap = BinaryHeap::new();
    for i in 0..n {
        heap.push(a[i]);
    }

    for _ in 0..m {
        if let Some(k) = heap.pop() {
            heap.push(k / 2);
        }
    }
    let ans = heap.iter().fold(0, |sum, x| sum + x);
    println!("{}", ans);
}


Measured memory_bytes: 9592
N,K,S = map(int,input().split())
if S == 10**9:
    for i in range(K):
        print(S,end=" ")
    for i in range(N-K):
        print(1,end=" ")
else:
    for i in range(K):
        print(S,end=" ")
    for i in range(N-K):
        print(10**9,end=" ")

Measured memory_bytes: 50648
def main():
    N = int(input())
    ABC = [list(map(int, input().split())) for _ in range(N)]

    dp = [[0, 0, 0] for _ in range(N)]

    dp[0][0] = ABC[0][0]
    dp[0][1] = ABC[0][1]
    dp[0][2] = ABC[0][2]

    for i in range(1, N):
        for j in [0, 1, 2]:
            score = max(dp[i - 1][(j + 1) % 3], dp[i - 1][(j + 2) % 3]) + ABC[i][j]
            if score > dp[i][j]:
                dp[i][j] += score

    print(max(dp[-1]))


if __name__ == '__main__':
    main()


Measured memory_bytes: 47320
n,a,b = map(int, input().split())
ans = 0

for i in range(1, n+1):
    tmp_num = i
    tmp_sum = 0
    
    while tmp_num > 0:
        tmp_sum += tmp_num % 10
        tmp_num //= 10
    
    if a <= tmp_sum <= b:
        ans += i
    
print(ans)

Measured memory_bytes: 2940
#include<stdio.h>
#include<math.h>
int main(){
	int i,j,k;
	scanf("%d%d%d",&i,&j,&k);
	int s1,s2,s3;
	s1=fabs(i-j);
	s2=fabs(j-k);
	s3=fabs(k-i);
	int max=s1;
	if(max<s2)
		max=s2;
	if(max<s3)
		max=s3;
		if(max==s1){
			printf("%d",s2+s3);
			return 0;
		}
		if(max==s2){
			printf("%d",s1+s3);
			return 0;
		}if(max==s3){
			printf("%d",s2+s1);
			return 0;
		}
}

Measured memory_bytes: 128
// AtCoder Beginner Contest 123 - Problem A: Five Antennas (https://atcoder.jp/contests/abc123/tasks/abc123_a)
#include <bits/stdc++.h>

using namespace std;

string solve(vector<int>& xs, int k)
{
    for (int i = 0; i < 5; ++i)
        for (int j = i + 1; j < 5; ++j)
            if (xs[j] - xs[i] > k)
                return ":(";

    return "Yay!";
}

int main()
{
    ios::sync_with_stdio(false);

    vector<int> xs(5);

    for (int i = 0; i < 5; ++i)
        cin >> xs[i];

    int k;
    cin >> k;

    auto ans = solve(xs, k);

    cout << ans << '\n';

    return 0;
}


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

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

  int K,A,B; cin >> K >> A >> B;

  int b = 1;
  // +1/1回 or +B-A/2回
  if(B-A <= 2) b += K;
  else {
    K -= A-b, b += A-b;
    b += (B-A)*(K/2) + (K%2);
  }
  cout << b << endl;

  return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"strconv"
)

type priorityQueue []int

func (p priorityQueue) Len() int            { return len(p) }
func (p priorityQueue) Less(i, j int) bool  { return p[i] > p[j] }
func (p priorityQueue) Swap(i, j int)       { p[i], p[j] = p[j], p[i] }
func (p *priorityQueue) Push(x interface{}) { *p = append(*p, x.(int)) }
func (p *priorityQueue) Pop() interface{} {
	old := *p
	n := len(old)
	x := old[n-1]
	*p = old[0 : n-1]
	return x
}

func main() {
	var n, m int
	fmt.Scan(&n, &m)

	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	ts := make(map[int][]int)
	for i := 0; i < n; i++ {
		sc.Scan()
		a, _ := strconv.Atoi(sc.Text())
		sc.Scan()
		b, _ := strconv.Atoi(sc.Text())
		ts[a] = append(ts[a], b)
	}

	pq := make(priorityQueue, 0, n)
	heap.Init(&pq)
	ans := 0
	for i := 1; i <= m; i++ {
		if _, ok := ts[i]; ok {
			for _, v := range ts[i] {
				heap.Push(&pq, v)
			}
		}
		if len(pq) > 0 {
			ans += heap.Pop(&pq).(int)
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 11264
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
using ll = long long;
int INF = 1000000009;
int main()
{
    int n;
    cin >> n;
    vector<int> c(n - 1), s(n - 1), f(n - 1);
    rep(i,n-1){
        cin >> c[i] >> s[i] >> f[i];
    }
    for(int i = 0;i < n-1;i++){
        int now = s[i] + c[i];
        for (int j = i + 1; j < n-1; j++)
        {
            if(now <= s[j]){
                now = s[j] + c[j];
            }else{
                now = s[j] + (now - s[j] + f[j] - 1) / f[j] * f[j] + c[j];
            }
        }
        cout << now << endl;
    }
    cout << 0 << endl;
}

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

typedef pair<int, int> P;
typedef long long ll;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repto(i, n) for(int i = 0; i <= (n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define mp make_pair
#define INF 1145141919
#define MOD 1000000007
#define DEBUG(x) cout << #x << ": " << x << endl;
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }

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

  int N, M;
  cin >> N >> M;
  vector<vector<int> > v(N);
  queue<int> que;
  rep(i, M) {
    int A, B;
    cin >> A >> B;
    A--;
    B--;
    v[B].pb(A);
    v[A].pb(B);
  }
  // rep (i, v.size()) {
  //   rep(j, v[i].size()) {
  //     cout << v[i][j] << ' ';
  //   }
  //   cout << endl;
  // }
  int p = 0;
  int cnt = N-1;
  vector<int> ans(N);
  vector<bool> seen(N, true);
  que.push(p);
  while (!que.empty()) {
    p = que.front();
    que.pop();
    for (int i = 0; i < v[p].size(); i++) {
      int t = v[p][i];
      if (seen[t] == true) {
        que.push(t);
        seen[t] = false;
        ans[t] = p;
        cnt--;
      }
    }
  }
  if (cnt > 0) {
    cout << "No" << endl;
    // cout << cnt << endl;
    // for (int i = 1; i < N; i++) {
    //   cout << ans[i]+1 << endl;
    // }
  }
  else {
    cout << "Yes" << endl;
    for (int i = 1; i < N; i++) {
      cout << ans[i]+1 << endl;
    }
  }
}


Measured memory_bytes: 10044
N = int(input())
S = []
for i in range(N):
    S.append(input())

def check(S, A, B):
    for i in range(N):
        for j in range(i+1, N):
            if S[i][j] != S[j][i]:
                return 0
    return 1

cnt = 0
for i in range(N):
    cnt += check(S[i:] + S[:i], 0, i)
print(cnt * N)

Measured memory_bytes: 3188
#include <cassert>
#include <functional>
#include <vector>

template <typename CommutativeMonoid>
class FenwickTree {

public:
	using value_type = CommutativeMonoid;
	using reference = value_type &;
	using const_reference = const value_type &;
	using container_type = std::vector<value_type>;
	using size_type = typename container_type::size_type;

private:
	const size_type size_, capacity;
	container_type tree;
	static size_type getsize(const size_type &size) noexcept {
		size_type ret = 1;
		while (ret < size)
			ret <<= 1;
		return ret;
	}

public:
	explicit FenwickTree(const size_type &size)
		: size_(size), capacity(getsize(size_)), tree(capacity + 1) {}
	void update(size_type index, const_reference diff) {
		assert(index < size());
		for (++index; index <= capacity; index += index & ~index + 1)
			tree[index] = tree[index] + diff;
	}
	value_type range(size_type end) const {
		assert(end <= size());
		value_type ret;
		for (; end; end &= end - 1)
			ret = tree[end] + ret;
		return ret;
	}
	size_type search(const std::function<bool(const_reference)> &b) const {
		if (b(value_type()))
			return 0;
		if (!b(tree.back()))
			return size() + 1;
		size_type i = 0, k = capacity;
		value_type acc;
		while (k >>= 1)
			if (!b(acc + tree[i | k]))
				acc = acc + tree[i |= k];
		return i + 1;
	}
	size_type size() const noexcept { return size_; }
	bool empty() const noexcept { return !size_; }
};

#include<cstdint>
template <typename T> struct Sum {
	using value_type = T;
	using size_type = std::uint_fast32_t;
	T a;
	size_type s;
	explicit Sum(const T &x = T(0), const size_type y = 0) : a(x), s(y) {}
	Sum operator+(const Sum &o) const { return Sum(a + o.a, s + o.s); }
	Sum operator-(const Sum &o) const { return Sum(a - o.a, s - o.s); }
};

#include <iostream>
int main(void) {
	using S = Sum<int>;
	int n, q;
	std::cin >> n >> q;
	FenwickTree<S> T(n);
	while (q--) {
		int c, x, y;
		std::cin >> c >> x >> y;
		if (c)
			std::cout << (T.range(y) - T.range(x - 1)).a << std::endl;
		else
			T.update(x - 1, S(y));

	}
	return 0;
}



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

using namespace std;

#ifndef ONLINE_JUDGE
  #define pr_debug(...) do { printf("DEBUG: line %d: %s: ", __LINE__, __PRETTY_FUNCTION__); printf(__VA_ARGS__); } while(0)
  #define pr_vars(...) do { pr_debug(" "); pr_var(split(#__VA_ARGS__, ',').begin(), __VA_ARGS__); } while(0)
#else
  __attribute__ ((constructor)) static void fast_cin() { ios_base::sync_with_stdio(false); cin.tie(0); }
  #define pr_debug(...) do { } while(0)
  #define pr_vars(...) do { } while(0)
#endif /* ONLINE_JUDGE */

using ll = int64_t;
using ull = uint64_t;
#define X first
#define Y second
#define pb push_back

template<typename T> ostream &operator<< (ostream &fout, const vector<T> &vec)
{ for (const auto &el : vec) fout << el << ' '; return fout; }

template<typename T> istream &operator>> (istream &fin, vector<T> &vec)
{ for (size_t i = 0; i < vec.size(); i++) fin >> vec[i]; return fin; }

vector<string> split(const string &s, char c) { vector<string> v; ull st = 0, fn = 0, lvl = 0;
for ( ; fn < s.size(); fn++ ) { if (s[fn] == c && lvl == 0) { v.push_back(s.substr(st, fn - st)); st = fn + 1; }
if (s[fn] == '(') { lvl++; } if (s[fn] == ')') { lvl--; } } v.push_back(s.substr(st, fn - st)); return v; }

void pr_var(vector<string>::iterator it) { (void) it; cout << endl; }
template<typename T, typename... Args> void pr_var(vector<string>::iterator it, T a, Args... args)
{ cout << *it << "=" << a << "  "; pr_var(++it, args...); }

ll div_ceil(ll n, ll d) { ll res = n / d; if (res >= 0) res += n % d ? 1 : 0; return res; }
ll gcd(ll a, ll b) { a = llabs(a); b = llabs(b); while (a && b) a > b ? a %= b : b %= a; return a + b; }
ll lcm(ll a, ll b) { ll c = gcd(a, b); return c == 0 ? 0 : llabs(a / c * b); }

#define setp(a) fixed << setprecision(a)
const double PI = acos(-1.0);
constexpr double EPS = 1e-9;
constexpr double INF = 2e18;

using mp = pair<ll, ll>;
using mt = tuple<ll, ll, ll>;    // unpack: tie(ll, ll, ll) = mt;

constexpr ll MAX = 1e5 + 5;

char arr[MAX];

int main()
{
    ll n; cin >> n;
    map<ll, ll> m;
    for (ll i = 0; i < n; i++) {
        ll a; cin >> a;
        m[a]++;
    }
    ll res = 0;
    for (auto i: m)
        if (i.Y % 2 == 1)
            res++;
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 6528
#include <bits/stdc++.h>
    using namespace std;
     
    int main() {
      int n, l, r, x=0;
      cin >> n;
      
      for (int i=0; i < n; i++){
        cin >> l >> r;
        x += r - l + 1;
      }
      
      cout << x << endl;

    }

Measured memory_bytes: 256
import java.util.Scanner

object Main extends App {
  val sc = new Scanner(System.in)

  val n = sc.nextInt
  val s, t = sc.next
  val ans = (0 until n)
    .map(i => (i, s.substring(i), t.substring(0, n - i)))
    .find(t => t._2 == t._3)
    .map(n + _._1)
    .getOrElse(2 * n)
  println(ans)
}


Measured memory_bytes: 25548
#include <bits/stdc++.h>
#define s second
#define f first
#define ll long long
using namespace std;
const int mod = 1e9+7 , N = 1e5+5;
ll fact[N] , INV[N] , a[N] ;
ll fastpower ( ll b , ll p) {
    if ( p == 0) return 1 ;
    ll halfpower = fastpower(b,p/2)%mod ;
    halfpower = (halfpower*halfpower)%mod ;
    if ( p%2) halfpower = (halfpower * b) %mod ;
    return halfpower %mod ;
}
void pre() {
    fact[0] = 1 ;
    fact[1] = 1 ;
    for ( ll i = 2 ; i < N ; i++)
        fact[i] = ( i * fact[i-1])%mod;
   for ( int i = 0 ; i < N ; i++)
        INV[i] = fastpower(fact[i],mod-2);
}
ll nCr ( int n , int r) {
   return (((fact[n]*INV[n-r])%mod)*INV[r])%mod;
}
int main()
{
    pre();
    ll mx = 0 , mn = 0 , ans = 0 ;
    int n ,k ;
    cin >> n >> k ;
    for ( int i = 1 ; i <= n ; i++) cin >> a[i];
    sort(a+1,a+n+1) ;
    for ( int i = 1 ; i <= n ; i++) {
          if ( i-1 >= k-1)
        mx = (((nCr(i-1,k-1)) * a[i])%mod)%mod ;
          if (n-i >= k-1)
        mn = (((nCr(n-i,k-1)) * a[i])%mod)%mod ;
       ans = ((ans%mod) +(mx - mn ))%mod ;
       if (ans < 0 ){
       ans += mod ;
       ans %= mod ;
       }
       mx = 0 , mn = 0 ;
    }
    cout << ans ;
}


Measured memory_bytes: 2560
#include <stdio.h>

int main(void) {
	int a, b, c;
	int i, ans;
	
	scanf("%d %d %d", &a, &b, &c);
	
	ans = 0;
	for (i = a; i <= b; i++) if (c % i == 0) ans++;
	
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 596
n, m = map(int, input().split())
AB = []
for i in range(n):
    a,b = map(int, input().split())
    AB.append((a, b))
AB.sort()

ans = 0
for i in range(m):
    a, b = AB[i]
    if b >= m:
        ans += a*m
        break
    else:
        ans += a*b
        m -= b
print(ans)


Measured memory_bytes: 83284
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <math.h>
#include <algorithm> // sort

#define REP(i, n) for (long long i = 0; i < (n); i++) 
typedef long long ll;
static const ll INF = 1000000000000000000LL;
using namespace std;

const int MOD = 1000000007;

//h,n,w

int main(){
    ll N;
    cin >> N;

    for(ll h = 1; h <= 3500; ++h)
    {
        for(ll n = 1; n <= 3500; ++n)
        {
            //4   1   1   1
            //- = - + - + -
            //N   h   n   w

            //h,wを決め打ってwが正整数となるか
            ll nume = N*h*n;
            ll denom = 4*h*n - N*n - N*h;
            //4*h*n*w = N*n*w + N*h*w + N*h*n
            //w = (N*h*n) / (4*h*n - N*n - N*h);
            if(denom <= 0)continue;
            if(nume  %  denom == 0 && nume / denom <= 3500)
            {
                ll w = nume / denom;
                cout << h << " ";
                cout << n << " ";
                cout << w << endl;
                return 0;
            }
        }
    }

    return 0;    
}



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

using namespace std;
using ll = long long;

int main() {
    ll h, w;
    cin >> h >> w;
    if (h == 1 || w == 1) {
        cout << 1 << endl;
    } else {
        ll a = (w + 1) / 2;
        ll b = w / 2;
        ll ans = (ll)a * ll((h + 1) / 2) + (ll)b * ll(h / 2);
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <climits>
#include <complex>
#include <fstream>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <thread>
#include <tuple>
#include <type_traits>
#include <vector>

#include <stdio.h>

using ll = long long;
using namespace std;

vector<vector<bool>> v;

int main() {
    ios::sync_with_stdio(false);
    string s, t;
    cin >> s >> t;

    for (int i = s.size() - t.size() + 1; i >= 0; i--) {
        bool ok = true;
        for (int j = 0; j < t.size(); j++) {
            if (s[i + j] == '?' || s[i + j] == t[j])
                continue;
            else {
                ok = false;
                break;
            }
        }
        if (ok) {
            // answer found
            for (int j = 0; j < t.size(); j++) {
                s[i + j] = t[j];
            }
            for (int k = 0; k < s.size(); k++) {
                if (s[k] == '?')
                    s[k] = 'a';
            }
            cout << s << endl;
            return 0;
        }
    }

    cout << "UNRESTORABLE " << endl;
    return 0;
}


Measured memory_bytes: 3132
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <list>
#include <map>

using namespace std;

const int N = 100005;

int n, k;
string a;
int pref[N];

int sum(int x, int y) {
  return (pref[y] - (x > 0 ? pref[x - 1] : 0));
}

int main() {
  cin >> n >> k >> a;
  pref[0] = (a[0] == '0');
  for (int i = 1; i < n; i++) {
    pref[i] = pref[i - 1] + (a[i] == '0' && a[i - 1] == '1');
  }
  int res = 0;
  for (int i = 0; i < n; i++) {
    if (!(i == 0 || (a[i] == '1' && a[i - 1] == '0'))) continue;
    int l = i, r = n - 1, ans = -1;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (sum(i, mid) <= k) {
        ans = mid;
        l = mid + 1;
      } else {
        r = mid - 1;
      }
    }
    if (ans != -1) res = max(res, ans - i + 1);
  }
  cout << res << endl;
  return 0;
}


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

typedef long long ll;
#define SZ(a) (int)a.size()
#define PB push_back
//#define cerr if(false)cerr
#define print(x) cerr<<"\n" << (#x) << " is " << (x) << endl;



int32_t main(){
	int arr[3];
	for(int i=0; i<3; i++) 
		cin >> arr[i];
	sort(arr, arr+3);
	int dist = 0;
	int prev = -1;
	for(int i=1; i<3; i++)
		if(arr[i] != arr[i-1])
			dist++;
	if(dist == 1)
		cout << "Yes" << endl;
	else cout << "No" << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int N, M;
	scanf("%d %d", &N, &M);
	int a[M];
	int b[M];
	int co;
	int un;
	int C[N];
	
	for(un = 0; un < N; un++)
	{
		C[un] = 0;
	}
	
	
	for(co = 0; co < M; co++)
	{
		scanf("%d %d", &a[co], &b[co]);
	}
	
	for(un = 0; un < N; un++)
	{
		for(co=0; co<M; co++)
		{
			if (a[co] == un+1) C[un]++ ;
			if (b[co] == un+1) C[un]++;
		}
		printf ("%d\n", C[un]);
	}
	

return 0;
}	
	

Measured memory_bytes: 128
N=int(input())
V=list(map(int,input().split()))
C=list(map(int,input().split()))
D=[]
a=0
for i in range(len(C)):
    D.append(V[i]-C[i])
for i in range(len(D)):
    if D[i]>=1:
        a+=D[i]
print(a)

Measured memory_bytes: 8992
#include <stdio.h>
#include <string.h>
int main(void){
    int n,l,i,j;
    char s[101][101];
    char tmp[101];
    scanf("%d%d",&n,&l);
    for(i=0;i<n;i++)
        scanf("%s",s[i]);
    
    for(i=0;i<n;i++){
        for(j=i+1;j<n;j++){
            if(strcmp(s[i],s[j])>0){
                strcpy(tmp,s[i]);
                strcpy(s[i],s[j]);
                strcpy(s[j],tmp);
            }
        }
    }
    for(i=0;i<n;i++)
        printf("%s",s[i]);
}


Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>
#define int long long
#define rep(i, n) for (int i = 0; i < (n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FORR(i,a,b)for(int i=(a);i<=(b);i++)
#define repR(i,n) for(int i=n;i>=0;i--)
#define P pair<int, int>
#define sz(x) x.size()
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define VE vector<int>
#define COUT(x) cout<<(x)<<endl
#define MA map<int,int>
#define SE set<int>
#define PQ priority_queue
#define COUT(x) cout<<(x)<<endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl

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

using namespace std;
typedef long long ll;
using Graph = vector<vector<int>>;
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}
bool compare_by_b(pair<int, int> a, pair<int, int> b) {
	if (a.second != b.second) {
		return a.second < b.second;
	}
	else {
		return a.first < b.first;
	}
}

const long long MOD = 1000000007;
const long long INF = 1LL << 50;

// pair -> vector<pair<int,int>> 
//		   AandB.push_back(make_pair(a[i],b[i]))

int h[101010];
int dp[101010];

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, k; cin >> n >> k;
	rep(i, n)cin >> h[i];
	rep(i, 101010)dp[i] = INF;
	dp[0] = 0;
	rep(i, n) {
		FOR(j,1,k+1) {
			chmin(dp[i + j], dp[i] + abs(h[i] - h[i + j]));
		}
	}
	cout << dp[n-1] << endl;
	return 0;
}

Measured memory_bytes: 1792
#include<stdio.h>

int lcm(int a,int b){
    int m;
    int p=a*b;
    m = a%b;
    while(m>0){
        a = b;
        b = m;
        m = a%b;
    }
    return p/b;
}

main(){
    int n,a,b;
    scanf("%d",&n);
    scanf("%d %d",&a,&b);
    a = lcm(a,b);
    while(n>2){
        scanf("%d",&b);
        a = lcm(a,b);
        n--;
    }
    printf("%d\n",a);
}

Measured memory_bytes: 1024
#include <algorithm>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>

using namespace std;

typedef long long ll;
// constexpr ll MOD = 998244353;
constexpr ll MOD = 1000000007;

// struct UnionFind {
//     vector<ll> par;
//     vector<ll> siz;
    
//     UnionFind(ll N): par(N), siz(N,1) {
//         for (ll i=0;i<N;i++) par[i] = i;
//     }

//     ll root(ll x) {
//         if (par[x] == x) return x;
//         else return par[x] = root(par[x]);
//     }

//     void unite(ll x, ll y) {
//         ll rx = root(x);
//         ll ry = root(y);
//         if (rx == ry) return;
//         // if (siz[rx] < siz[ry]) swap(rx,ry);
//         par[rx] = ry;
//         siz[ry] += siz[rx];
//     }

//     bool same(ll x, ll y) {
//         ll rx = root(x);
//         ll ry = root(y);
//         return rx == ry;
//     }

//     ll size(ll x) {
//         return siz[root(x)];
//     }
// };

//     vector<ll> par;
//     vector<ll> siz;
    
//     UnionFind(ll N): par(N), siz(N,1LL) {
//         for (ll i=0;i<N;i++) par[i] = i;
//     }

//     ll root(ll x) {
//         if (par[x] == x) return x;
//         else return par[x] = root(par[x]);
//     }

//     void unite(ll x, ll y) {
//         ll rx = root(x);
//         ll ry = root(y);
//         if (rx == ry) return;
//         par[rx] = ry;
//         siz[ry] += siz[rx];
//     }

//     bool same(ll x, ll y) {
//         ll rx = root(x);
//         ll ry = root(y);
//         return rx == ry;
//     }

//     ll size(ll x) {
//         return siz[root(x)];
//     }
// };

int main(void) {
    int A, B;
    cin >> A >> B;
    cout << A*B << endl;

    return 0;
}


Measured memory_bytes: 3588
class Dice
	def initialize(n=Array.new(6,0))
		@num = n
		@LRRoll = [:u, :b, :d, :f]
		@FBRoll = [:u, :l, :d, :r]
		@UDRoll = [:r, :b, :l, :f]
		reset
	end

	def reset
		@position = { u: @num[0],
									d: @num[5],
									r: @num[2],
									l: @num[3],
									f: @num[4],
									b: @num[1]
		}
	end

	def move(v)
		case v
		when "N"
			Roll(@LRRoll)
		when "S"
			Roll(@LRRoll, -1)
		when "E"
			Roll(@FBRoll)
		when "W"
			Roll(@FBRoll, -1)
		end
	end

	def move_roll(n)
		n.times { Roll(@UDRoll) }
	end

	def Roll(roll, v=1)
		v = -1 if v != 1
		t = @position[roll[0]]
		@position[roll[  0]] = @position[roll[1*v]]
		@position[roll[1*v]] = @position[roll[2*v]]
		@position[roll[2*v]] = @position[roll[3*v]]
		@position[roll[3*v]] = t
	end

	def v_up
		@position[:u]
	end

	def v_down
		@position[:d]
	end

	def v_foward
		@position[:f]
	end

	def v_back
		@position[:b]
	end

	def v_right
		@position[:r]
	end

	def v_left
		@position[:l]
	end

end

def SameDice?(d1, d2)
	same = false

	3.times {
		break if d1.v_up == d2.v_up and d1.v_down == d2.v_down
		d2.move("E")

		break if d1.v_up == d2.v_up and d1.v_down == d2.v_down
		d2.move("N")
	}

	same = true if d1.v_up == d2.v_up and d1.v_down == d2.v_down

	if same
		case d1.v_back
		when d2.v_left
		d2.move_roll(1)
		when d2.v_foward
			d2.move_roll(2)
		when d2.v_right
			d2.move_roll(3)
		when d2.v_back
			same = true
		else
			same = false
		end
	end

	if same
		same = false if not  (d1.v_foward == d2.v_foward and
													d1.v_right  == d2.v_right  and
											 		d1.v_left   == d2.v_left)
	end

	same
end

d = Array.new
gets.to_i.times {
	n = gets.chomp.split(" ").map &:to_i
	d << Dice.new(n)
}

alldiff = true

for i in 0...d.length-1
	for j in i+1...d.length
		alldiff = false if SameDice?(d[i], d[j])
		break unless alldiff
	end
	break unless alldiff
end

if alldiff
	print("Yes\n")
else
	print("No\n")
end

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

int main() {
	int A, B, T;
	cin >> A >> B >> T;
	int ans = 0;
	for (int i = 1; i <= T; i++){
		if (i%A == 0) ans += B;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3620
/**
 *    author:  tourist
 *    created: 02.09.2017 15:17:17       
**/
#include <bits/stdc++.h>

using namespace std;

int a[1234567];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", a + i);
    a[i]--;
  }
  int ans = 0;
  for (int i = 0; i < n; i++) {
    if (a[i] == i) {
      if (i + 1 < n && a[i + 1] == i + 1) {
        ans++;
        i++;
        continue;
      }
      ans++;
    }
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <functional>
#include <algorithm>
#include <vector>
#include <cstdlib>
using namespace std;

bool is_valid(vector<bool>&a) {
	if (a.size() == 1)return true;
	for (auto itr = a.begin(); itr != a.end() - 1; ++itr) {
		if (*itr == true && *(itr + 1) == true) {
			return false;
		}
	}
	return true;
}
long long int searchroute(vector<int>& Wexists, vector<int>& Wnexists, int H,int W,int K,int pos) {
	long long int num = 0;
	static vector<pair<vector<int>,long long int> >memo;

	if (H == 0&&K==pos)return 1;
	if (abs(K - pos) > H)return 0;
	for (auto a : memo) {
		if (a.first[0] == H&&a.first[1] == W&&a.first[2] == K&&a.first[3] == pos) {
			return a.second;
		}
	}
	num+=Wnexists[pos-1]*searchroute(Wexists,Wnexists, H - 1, W, K, pos)%1000000007;
	if (pos != 1)num +=Wexists[pos-2]*searchroute(Wexists, Wnexists, H - 1, W, K, pos - 1) % 1000000007;
	if (pos != W)num +=Wexists[pos-1]*searchroute(Wexists, Wnexists, H - 1, W, K, pos + 1) % 1000000007;
	num %= 1000000007;
	pair<vector<int>, long long int> aa({ H,W,K,pos},num) ;
	memo.push_back(aa);
	return num;
}
int main() {
	int H, W, K;
	cin >> H >> W >> K;
	//i列とi+1列の間の線をiとする0->W-2
	if (W == 1) {
		cout << 1<<endl;
		return 0;
		//幅１の場合必ず1
	}
	vector<bool> valid(W - 1, false);
	vector<vector<bool> > valids;
	vector<int> Wexsists(W-1,0);//某の間に存在する
	vector<int> Wnexsists(W,0);//某i-1の左右に存在しない
	bool flag = true;
	while(flag){
		if (is_valid(valid)) {
			//std::vector<bool> tmp;
			valids.push_back(valid);
			//copy(valid.begin(), valid.end(), back_inserter(valids));
		}
		for (auto itr = valid.begin(); itr != valid.end(); ++itr) {
			if (*itr == false) {
				*itr = true;
				break;
			}else {
				if (itr == valid.end() - 1) {
					flag = false;
				}
				else {
					*itr = false;
				}
			}
		}
		//if (!flag)break;
	}
	for (auto a : valids) {
		//for (auto b : a) { cout << b; }
		//cout << endl;
		for (int i = 0; i < W - 1;++i) {
			if (a[i] == true) {
				Wexsists[i] += 1;
			}
			if (i != W - 2) {
				if (a[i] == false && a[i+1] == false) {
					Wnexsists[i + 1] += 1;
				}
			}
		}
		if (a[0] == false)Wnexsists[0] += 1;
		if (a[W - 2] == false)Wnexsists[W - 1] += 1;
		//cout << endl;
	}
	/*for (auto a : Wnexsists) {
		cout << a;
	}cout << endl;*/
	cout << searchroute(Wexsists, Wnexsists, H, W, K, 1);
	return 0;
}





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

const ll mod = 1000000007;
const int INF = 1001001001;

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

int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);
	int n; cin >> n;
	vector<int> a(n);
	vector<int> num(1000001);
	set<int> st;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		num[a[i]]++;
		st.insert(a[i]);
	}
	int mx = *max_element(a.begin(), a.end());
	int full = a[0];
	bool ok1 = false, ok2 = false;
	for(int i = 1; i < n; i++){
		full = gcd(full, a[i]);
		if(full == 1){
			ok1 = true;
			break;
		}
	}
	for(int i = 2; i <= mx; i++){
		int cnt = 0;
		for(int j = 1; j * i <= mx; j++){
			int tmp = i * j;
			if(tmp > mx) break;
			if(st.count(tmp)){
				cnt += num[i * j];
			}
			if(cnt >= 2){
				ok2 = true;
				break;
			}
		}
		if(ok2) break;
	}
	if(!ok2) cout << "pairwise coprime" << endl;
	else if(ok2 && ok1) cout << "setwise coprime" << endl;
	else cout << "not coprime" << endl;

} 

Measured memory_bytes: 57804
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 998244353;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-11;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
int n; int cnt;
vector<int> G[1 << 18];
ll lazy[1 << 18];
struct uf {
	vector<int> par,num;
	void init(int n_) {
		par.resize(n_);
		num.resize(n_);
		rep(i, n_) {
			par[i] = i;
			num[i] = 1;
		}
	}
	int find(int x) {
		if (par[x] == x)return x;
		else return par[x] = find(par[x]);
	}
	void unite(int x, int y, ll c) {
		x = find(x), y = find(y);
		par[x] = par[y] = cnt;
		G[cnt].push_back(x);
		G[cnt].push_back(y);
		lazy[x] += num[y] * c;
		lazy[y] += num[x] * c;
		num[cnt] = num[x] + num[y];
		cnt++;
	}
};
struct edge { 
	int fr, to; ll cost;
	bool operator<(const edge &e)const {
		if (cost != e.cost)return cost > e.cost;
		if (fr != e.fr)return fr > e.fr;
		return to > e.to;
	}
};
edge e[1 << 17];
int main() {
	cin >> n; cnt = n;
	uf u; u.init(2*n);
	rep(i, n-1) {
		int a, b; cin >> a >> b; a--; b--; ll c; cin >> c;
		e[i] = { a,b,c };
	}
	sort(e, e + n - 1);
	rep(i, n - 1) {
		u.unite(e[i].fr, e[i].to, e[i].cost);
	}
	queue<int> q; q.push(cnt - 1);
	while (!q.empty()) {
		int id = q.front(); q.pop();
		rep(j, G[id].size()) {
			int to = G[id][j];
			q.push(to);
			lazy[to] += lazy[id];
		}
	}
	rep(i, n) {
		cout << lazy[i] << endl;
	}
	//stop
	return 0;
}


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

#define rep(X,N) for(ll X = 0; X < (N); X++)
#define PI (acos(-1.0))
#define pback push_back
#define mpair make_pair
#define MODN 1000000007
#define ALL(V) (V).begin(),(V).end()
#define INT_MAX_HALF (INT_MAX / 2)
#define EPS (1e-10)

using namespace std;
typedef long long ll;


int main(){

    int n;
    cin >> n;

    vector<int> count(26, INT_MAX);

    rep(i, n){
        string s;
        cin >> s;

        vector<int> tmpcount(26);

        rep(j, s.size()){
            tmpcount[s[j] - 'a']++;
        }

        rep(j, 26){
            count[j] = min(count[j], tmpcount[j]);
        }
    }

    rep(i, 26){

        rep(j, count[i]){
            cout << (char)('a' + i);
        }
    }

    cout << endl;


    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  #define int long
  int N,T;cin>>N>>T;
  vector<int> A(N),B(N);
  
  vector<pair<int,int>>p(N);
  
  for(int i=0;i<N;i++){
    int a,b;cin>>a>>b;
    p[i].first=a;p[i].second=b;
  }sort(p.begin(),p.end());
  
  for(int i=0;i<N;i++){
    A[i]=p[i].first;B[i]=p[i].second;
  }
  
  int tmax=0;
  for(int i=0;i<N;i++){if(tmax<A[i])tmax=A[i];}
  tmax=3000;
  vector<vector<int>>DP(T+1+tmax*2,vector<int>(N,0));
  int ans=0;
  for(int j=1;j<T+1+tmax*2;j++){
    for(int i=0;i<N;i++){
      //品物iを加えるかどうか
      if(j-A[i]>=0 && j-A[i]<T){
        if(i==0)DP[j][i]=B[i];
        else DP[j][i]=max(max(DP[j-1][i],DP[j][i-1]),DP[j-A[i]][i-1]+B[i]);
      }
      else{
        if(i==0)DP[j][i]=DP[j-1][i];
        else DP[j][i]=max(DP[j-1][i],DP[j][i-1]);
        
      }
      
      if(DP[j][i]>ans)ans=DP[j][i];
    }
  } 
  cout<<ans;
}







Measured memory_bytes: 211712
a = gets.to_i
# b = gets.to_i
# s = gets.chomp
# s,t = gets.split.map(&:to_s)
# a = gets.split.map(&:to_i)

# s = gets.chomp.chars.uniq
# puts gets.chomp.chars.uniq.size != 1 ? "Yes" : "No"

p a**2

Measured memory_bytes: 1788
#include<iostream>
using namespace std;
typedef long long int LL;
LL a[2][10005];
int main(){
	LL n;
	LL i,j,k;
	LL t[3]={0};
	bool s;
	cin>>n;
	for(i=0;i<2;i++){
		for(j=0;j<n;j++){
			cin>>a[i][j];
			t[i]+=a[i][j];
		}
	}
	t[1]-=t[0];
	if(t[1]<0)s=false;
	else{
		for(i=0;i<n;i++){
			if(a[0][i]>=a[1][i])continue;
			t[2]+=(a[1][i]-a[0][i]-1)/2+1;
		}
		if(t[2]<=t[1])s=true;
		else s=false;
	}
	if(s)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}
	


Measured memory_bytes: 384
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <string>
#include <iostream>
#include <cassert>
#include <cmath>
using namespace std;

int main() {
        vector<long long> a(3);
        for (int i = 0; i < 3; i ++) {
                scanf("%lld", &a[i]);
        }
        int k;
        scanf("%d", &k);
        sort(a.begin(), a.end());
        a.back() = a.back() * pow(2, k);
        long long ans = 0;
        for (int i = 0; i < 3; i ++) {
                ans += a[i];
        }
        printf("%lld\n", ans);
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
#define double long double
//typedef    long long          ll;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
//typedef    pair<int,int>      P;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+18;
const double EPS=1e-15;
const int MOD=1000000007;
 
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

signed main(){
	int n,e,t,x[100010] = {},ind = 0,tmp = INF,dp[100010];
	cin >> n >> e >> t;
	for(int i = 1;i <= n;i++){
		cin >> x[i];
		dp[i] = INF;
	}
	dp[0] = 0;
	for(int i = 1;i <= n;i++){
		while((x[i] - x[ind + 1]) * 2 >= t){
			chmin(tmp,dp[ind] + (x[i] - x[ind + 1]) * 2);
			ind++;
		}
		dp[i] = min(tmp,dp[ind] + t);
		tmp += (x[i + 1] - x[i]) * 2;
	}
	cout << dp[n] + e << endl;
	return 0;
}

Measured memory_bytes: 1920