akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A, B):
    return min(A*N, B)


def main():
    N, A, B = read_int_n()
    print(slv(N, A, B))


if __name__ == '__main__':
    main()


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

int main(void)
{
	char n[4];
	int cnt = 1;
	scanf("%s", n);
	for (int i = 1; i < 4; i++) {
		if (n[i] == n[i - 1])
		{
			cnt++;
			if (cnt == 3) goto end;
		}
		else cnt = 1;
	}
end:
	if (cnt >= 3) puts("Yes\n");
	else puts("No\n");
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <math.h>
#include <list>
#include <string>
using namespace std;

int main()
{
	string S;
	string tempS;
	long long K;
	cin >> S;
	cin >> K;

	tempS = S;
	if (S.size() == 1) {
		cout << K / 2 << endl;
	}
	else {
		long long cnt = 0;
		bool isAllSame = true;
		for (int i = 1; i < S.size(); i++) {
			if (S[i] != S[i - 1]) {
				isAllSame = false;
				break;
			}
		}
		if (isAllSame) {
			cout << (S.size()*K) / 2 << endl;
			return 0;
		}

		for (int i = 1; i < S.size(); i++) {
			if (S[i] == S[i - 1]) {
				cnt++;
				S[i] = 'C';
			}
		}
		if (S.front() != S.back()) {
			cout << K * cnt << endl;
		}
		else {
			char c = tempS[0];
			int howmany = 1;
			for (int i = 1; i < tempS.size(); i++) {
				if (tempS[i] == c) {
					howmany++;
				}
				else {
					break;
				}
			}
			for (int i = tempS.size() - 1; i >= 0; i--) {
				if (tempS[i] == c) {
					howmany++;
				}
				else {
					break;
				}
			}
			if (howmany%2 == 1) {
				cout << (K*cnt) << endl;
			}
			else {
				cout << (K*cnt) + (K - 1) << endl;
			}
		}
	}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef set<int> si;
typedef map<string, int> msi;
typedef long long ll;
const ll INF = 1e18L + 1;

int main()
{
  ll a, b, c;
  cin >> a >> b >> c;
  ll right = c - a - b;
  ll left = 4 * a * b;
  bool ok = false;
  if (left < right * right && right >= 0)
    ok = true;
  puts(ok ? "Yes" : "No");
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<ll> vl;
typedef vector<pair<ll,ll>> vp;
#define rep(i,n) for(ll i = 0; i < ll(n); i++)
#define ALL(x) (x).begin(), (x).end()
#define inputv(v,n) rep(i,n){\
    ll x;\
    cin>>x;\
    v.push_back(x);\
    }

const ll INF=99999999999999;
const ll MOD=1000000007;
 
int main() {
  ll n;
  string s;
  cin >> n >> s;
  ll cnt=0;
  ll m=0;
  ll p=0;
  rep(i,n){
    if(s[i] == '(') cnt++;
    if(s[i] == ')') cnt--;
    if(cnt < 0) m = max(m,-cnt);
  }
  rep(i,m) s = '(' + s;
  n += m;
  cnt = 0;
  rep(i,n){
    if(s[i] == '(') cnt++;
    if(s[i] == ')') cnt--;
  }
  rep(i,cnt) s = s+')';
  cout << s;
  
 return 0;
}

Measured memory_bytes: 256
package main

import (
        "fmt"
        "sort"
)

func solution(a, b, c int) int {
        memo := []int{a, b, c}
        sort.Ints(memo)
        hi := memo[2]
        lo := memo[0]
        mi := memo[1]
        if (hi-(hi-mi+lo))%2 == 1 {
                return hi - mi + 2 + (hi-(hi-mi+lo))/2

        }
        return hi - mi + (hi-(hi-mi+lo))/2
}

func abs(x int) int {
        if x < 0 {
                return -x
        }
        return x
}

func max(x, y int) int {
        if x > y {
                return x
        }
        return y
}

func min(x, y int) int {
        if x < y {
                return x
        }
        return y
}

func main() {
        var a, b, c int
        fmt.Scan(&a, &b, &c)
        fmt.Println(solution(a, b, c))
}

Measured memory_bytes: 1836
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

template<class T, bool directed>
class Dinic {
    void bfs(int s){
        fill(level.begin(),level.end(), -1);
        queue<int> Q;
        level[s] = 0;
        Q.emplace(s);
        while(!Q.empty()){
            int v = Q.front(); Q.pop();
            for (auto &&e : G[v]){
                if(e.cap > 0 && level[e.to] < 0){
                    level[e.to] = level[v] + 1;
                    Q.emplace(e.to);
                }
            }
        }
    }

    T dfs(int v, int t, T f){
        if(v == t) return f;
        for(int &i = iter[v]; i < G[v].size(); i++){
            edge &e = G[v][i];
            if(e.cap > 0 && level[v] < level[e.to]){
                T d = dfs(e.to, t, min(f,  e.cap));
                if(d == 0) continue;
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
        return 0;
    }
public:
    struct edge {
        int to{}; T cap; int rev{};
        edge() = default;
        edge(int to, T cap, int rev) : to(to), cap(cap), rev(rev) {}
    };

    vector<vector<edge>> G;
    vector<int> level, iter;
    Dinic() = default;
    explicit Dinic(int n) : G(n), level(n), iter(n) {}

    void add_edge(int from, int to, int cap){
        G[from].emplace_back(to, cap, G[to].size());
        G[to].emplace_back(from, directed ? 0 : cap,  G[from].size()-1);
    }


    T flow(int s, int t, T lim = INF<T>){
        T ret = 0;
        while(true) {
            bfs(s);
            if(level[t] < 0 || lim == 0) break;
            fill(iter.begin(),iter.end(), 0);
            while(true){
                T f = dfs(s, t, lim);
                if(f == 0) break;
                ret += f;
                lim -= f;
            }
        }
        return ret;
    }
};

int main() {
    int n, m, s, t;
    cin >> n >> m;
    Dinic<int, false> f(n);
    map<pair<int, int>, int> e;
    for (int i = 0; i < m; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        f.add_edge(a-1, b-1, 1);
        e[{a-1, b-1}] = i+1;
    }
    cin >> s >> t;
    s--; t--;
    vector<int> ans;
    cout << f.flow(s, t) << "\n";
    for (int i = 0; i < n; ++i) {
        for (auto &&j : f.G[i]) {
            if(j.cap != 0 && e.count({i, j.to})) ans.emplace_back(e[{i, j.to}]);
        }
    }
    cout << ans.size() << "\n";
    for (auto &&k : ans) {
        cout << k << "\n";
    }

    return 0;
}


Measured memory_bytes: 3364
#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <deque>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <unordered_map>
#include <bitset>
#include <sstream>

typedef  long long ll;
#define mop 1000000007
using namespace std;


unsigned long long nCr(long n, long r) {
    unsigned long long ans = 1;
    for (long i = 1 ; i < r + 1; ++i) {
        ans = ans * (n-i+1)/ i;
    }
    return ans;
}

int main() {
   

    ll n,a,b;
    cin >> n >> a >> b;
    vector <ll> v;
    for (ll i=0;i<n;i++){
        ll p;
        cin >> p;
        v.push_back(p);
    }
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());
    ll sum = 0;
    vector <ll> numlis;
    ll tmp = 0;
    for (ll i=0;i<a;i++){
        sum += v[i];
        if(i > 0 and v[i] != v[i-1]){
            tmp = 0;
        }
        tmp++;
    }

    ll r = tmp;
    for (ll i = a; i < n; i++) {
        if (i > 0 and v[i] != v[i - 1]) {
            break;
        }
        tmp++;
    }
    ll k = tmp;
    cout << fixed;
    cout << setprecision(8);
    cout << sum / (long double) (a) << endl;
    ll ans = 0;
    if(r != a) {
        // calculate kCr
       ans = nCr(k, r);
    }else{
        // calculate kCr, kC(r+1) , ..., kCb
        ans = 0;
        for (ll i=r;i<=min(b, k);i++){
            ans += nCr(k, i);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
	int A,B,C,D;
	int ret;
	ret=scanf("%d %d %d %d",&A,&B,&C,&D);
	while(1){
		C-=B;
		if(C<=0)break;
		A-=D;
		if(A<=0)break;
	}
	if(A>0){
		printf("Yes\n");
	}else{
		printf("No\n");
	}
}


Measured memory_bytes: 1616
import java.util.Scanner;

public class Main{

	public static void main(String args[]){
		new Main().mainrun();
	}

	private Scanner scan;
	private int n;
	private int[] a;

	public void mainrun() {
		scan = new Scanner(System.in);

		n = scan.nextInt();
		a = new int[n];

		for(int i = 0;i < n ; i++) {
			a[i] = scan.nextInt();
		}

		printElement();

		for(int i = 1;i < n;i++) {
			looprun(i);
		}
	}

	public void looprun(int index) {
		int v = a[index];

		int j = index - 1;

		while(j >= 0 && a[j] > v) {
			a[j + 1] = a[j];
			j--;
		}

		a[j + 1] = v;

		printElement();
	}

	private void printElement() {
		String str = Integer.toString(a[0]);

		for(int i = 1;i < n;i++) {
			str += " " + Integer.toString(a[i]);
		}

		System.out.println(str);
	}
}


Measured memory_bytes: 45772
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
from collections import defaultdict

N = int(input())

if N < 10:
    print(0)
    exit()


d = defaultdict(list)
d[2]=7
d[3]=4
d[5]=1
d[7]=1

#nの素因数分解(O(n**0.5)
def prime_factor(n):
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            if d[i] == []: d[i]=1
            else: d[i] += 1
            n = n//i
    if n != 1:
        if d[n] == []: d[n]=1
        else: d[n] += 1

for i in range(10,N+1):
    prime_factor(i)

cand2 = 0
cand4 = 0
cand14 = 0
cand24 = 0
cand74 = 0

for key,val in d.items():
    if val >= 2:
        cand2 += 1
        if val >=4:
            cand4 += 1
            if val >=14:
                cand14 += 1
                if val >=24:
                    cand24 += 1
                    if val >=74:
                        cand74 += 1


ans = 0
ans += cand4  * (cand4-1)//2 * (cand2-2)
ans += cand24 * (cand2-1)
ans += cand14 * (cand4-1)
ans += cand74

print(ans)



Measured memory_bytes: 3444
#include  <stdio.h>
#include <stdlib.h>

int a[100001] = { 0 };

int sort(const void *a, const void *b) {
	return *(int*)a - *(int*)b;
}

int main(void) {
	int N;
	long long int ans, x = 0, y = 0;

	scanf("%d", &N);
	for (int i = 0; i < N; i++) scanf("%d", &a[i]);
	qsort(a, N, sizeof(a[0]), sort);

	for (int i = N - 1; i > 0; i--) {
		if (a[i] == a[i - 1]) {
			if (x == 0) x = a[i];
			else {
				y = a[i];
				break;
			}
			i--;
		}
	}

	ans = x*y;
	printf("%lld\n", ans);

	return 0;
}

Measured memory_bytes: 892
fun main() {
    var (a, b, c, d) = readListInt()
    for (i in 1..10000) {
        if (i % 2 != 0) {
            c -= b
            if (c <= 0) {
                println("Yes")
                return
            }
        } else  {
            a -= d
            if (a <= 0) {
                println("No")
                return
            }
        }
    }
}

private fun read() = readLine()!!

private fun readInt() = read().toInt()

private fun readLong() = read().toLong()

private fun readDouble() = read().toDouble()

private fun readListString() = read().split(" ")

private fun readListInt() = readListString().map { it.toInt() }

private fun readListLong() = readListString().map { it.toLong() }

private fun readListDouble() = readListString().map { it.toDouble() }

private fun readMatrixString(n: Int): List<List<String>> {
    val matrix = mutableListOf<List<String>>()
    for (i in 0 until n) {
        val list = readListString()
        matrix.add(list)
    }
    return matrix
}

private fun readMatrixInt(n: Int): List<List<Int>> {
    val matrix = mutableListOf<List<Int>>()
    for (i in 0 until n) {
        val list = readListInt()
        matrix.add(list)
    }
    return matrix
}

private fun readMatrixDouble(n: Int): List<List<Double>> {
    val matrix = mutableListOf<List<Double>>()
    for (i in 0 until n) {
        val list = readListDouble()
        matrix.add(list)
    }
    return matrix
}

private fun readMatrixLong(n: Int): List<List<Long>> {
    val matrix = mutableListOf<List<Long>>()
    for (i in 0 until n) {
        val list = readListLong()
        matrix.add(list)
    }
    return matrix
}



Measured memory_bytes: 36340
import Data.List

solve :: [Int] -> [Int] -> String
solve x [a,b]
  | elemIndex a x > elemIndex b x = "Alice"
  | elemIndex a x < elemIndex b x = "Bob"
  | otherwise = "Draw"

main = getLine >>= putStrLn . solve ([2..13] ++ [1]) . map read . words

Measured memory_bytes: 508
n,*a=map(int,open(0).read().split())
x=s=l=c=0
for r,b in enumerate(a):
  x^=b
  s+=b
  while x<s:
    x^=a[l]
    s-=a[l]
    l+=1
  c+=r-l+1
print(c)


Measured memory_bytes: 91172
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010


int main(){
  string s;

  cin >> s;

  if(s == "A") cout << "T" << endl;
  if(s == "G") cout << "C" << endl;
  if(s == "C") cout << "G" << endl;
  if(s == "T") cout << "A" << endl;

  return 0;
}


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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

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

using namespace std;


using state=vector<vector<int>>;
const int inf=1<<29;
const int n=4,m=8;
	
// inline int hstar(const state &board){
// 	int ret=0;
// 	rep(i,n)rep(j,m-1) if(10*(i+1)+j+1!=board[i][j]) ret++;
// 	return ret;
// }

inline bool finish(const state &board){
	rep(i,n)rep(j,m-1) if(10*(i+1)+j+1!=board[i][j]) return false;
	return true;
}

int bfs(const state &board){
	map<state,int> dist;
	using elem=tuple<int,state>;
	priority_queue<elem,vector<elem>,greater<elem>> q;
	
	dist[board]=0;
	q.push(make_tuple(0,board));
	
	while(!q.empty()){
		int cost; state cboard;
		tie(cost,cboard)=q.top();q.pop();
		if(finish(cboard)) return dist[cboard];

		rep(i,n)rep(j,m){
			if(cboard[i][j]==0){
				state nboard=cboard;
				int left=cboard[i][j-1];
				rep(a,n)rep(b,m) if(cboard[a][b]==left+1) swap(nboard[a][b],nboard[i][j]);
				if(dist.find(nboard)!=end(dist)) continue;
				int d=dist[nboard]=dist[cboard]+1;
				q.push(make_tuple(d,nboard));
			}
		}
	}
	return -1;
}

int main(void){
	int t;
	cin >> t;
	while(t--){
		state board(4,vector<int>(8,0));
		rep(i,n)rep(j,1,m) cin >> board[i][j]; 
		rep(i,n)rep(j,m) rep(k,4) if(board[i][j]==10*(k+1)+1) swap(board[i][j],board[k][0]);
		cout << bfs(board) << endl;
	}
	return 0;
}

Measured memory_bytes: 27672
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define endl "\n"
const int MAX= 100005 ;
const long long mod = 1.0e9+7;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n,m,i;
    cin>>n>>m;
    ll arr[n];
    ll sum=0;
    priority_queue<ll,vector<ll>,greater<ll> > pq;
    for(i=0;i<n;i++)
    {
        cin>>arr[i];
        pq.push(arr[i]);
        //sum+=arr[i];
    }
    //sort(arr,arr+n);
    ll x,y,cnt=0,j;
    vector<pair<ll,ll> > v;
    for(i=0;i<m;i++)
    {
        cin>>x>>y;
        v.push_back({y,x});
    }
    sort(v.rbegin(),v.rend());
    for(i=0;i<m;i++)
    {
        x=v[i].second;
        y=v[i].first;
        for(j=0;j<x;j++)
        {
            cnt=pq.top();
            if(cnt<y)
            {
                pq.pop();
                pq.push(y);
            }
            else
            {
                break;
            }
        }
    }
    for(i=0;i<n;i++)
    {
        sum+=pq.top();
        pq.pop();
    }
    cout<<sum<<endl;
    return 0;
}

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

int main()
{
    string s;
    cin >> s;
    int i;
    bool check[26];
    for (i = 0; i < 26; i++)
    {
        check[i] = false;
    }
    for (i = 0; s[i] != '\0'; i++)
    {
        check[s[i] - 'a'] = true;
    }
    for (i = 0; i < 26; i++)
    {
        if (!check[i])
        {
            cout << (char)(i + 'a') << "\n";
            return 0;
        }
    }
    cout << "None"
         << "\n";
    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int main()
{
   string a,b,c;
   cin >> a >> b >> c;
  if (a[a.size()-1]==b[0] && b[b.size()-1] == c[0])
  { 
      cout << "YES\n";
      return 0;
   }
   cout << "NO\n";
   return 0;
}

Measured memory_bytes: 256
object Main extends App {
	var s = scala.io.StdIn.readInt

	def test(n: Int): Int = {
		if(n%2 == 0) n/2
		else 3*n + 1
	}

	var hit = Set[Int]()
	var ans = 1

	while(! hit(s)){
		hit += s
		s = test(s)
		ans += 1
	}

	println(ans)


}



Measured memory_bytes: 27332
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<string>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<unordered_set>
#define PI acos(-1)
#define pb push_back
#define all(x) x.begin(),x.end()
#define INF 0x3f3f3f3f
#define dd(x) cout<<#x<<" = "<<x<<","
#define de(x) cout<<#x<<" = "<<x<<"\n"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=55;
const int M=5005;
int cost[N][N],t[N][N];
int c[N],d[N];
ll a[N][M];
struct node{
	int id1,id2;
	ll v;
	bool operator <(node b)const { 
		return v>b.v;
	}
};
priority_queue<node> q;
int main()
{
	memset(cost,INF,sizeof(cost));
	memset(t,INF,sizeof(t));
	int n,m,s;
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=n;i++){
		for(int j=0;j<M;j++){
			a[i][j]=1e18;
		}
	}
	for(int i=1;i<=m;i++){
		int a,b,c,d;
		scanf("%d%d%d%d",&a,&b,&c,&d);
		cost[a][b]=cost[b][a]=c;
		t[a][b]=t[b][a]=d;
	}
	for(int i=1;i<=n;i++){
		scanf("%d%d",&c[i],&d[i]);
	}
	if(s>=5000){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				for(int k=1;k<=n;k++){
					t[j][k]=min(t[j][k],t[j][i]+t[i][k]);
				}
			}
		}
		for(int i=2;i<=n;i++){
			printf("%d\n",t[1][i]);
		}
	}
	else{
		q.push({1,s,0});
		a[1][s]=0;
		while(!q.empty()){
			node top=q.top();
			q.pop();
			int id1=top.id1,id2=top.id2;
			ll v=top.v;
//			dd(id1);dd(id2);de(v);
			if(id2<M-1){
				if(a[id1][min(M-1,id2+c[id1])]>v+d[id1]){
					a[id1][min(M-1,id2+c[id1])]=v+d[id1];
					q.push({id1,min(M-1,id2+c[id1]),v+d[id1]});
				}
			}
			for(int i=1;i<=n;i++){
				if(cost[id1][i]<=id2){
					if(a[i][id2-cost[id1][i]]>v+t[id1][i]){
						a[i][id2-cost[id1][i]]=v+t[id1][i];
						q.push({i,id2-cost[id1][i],v+t[id1][i]});
					}
				}
			}
		}
		for(int i=2;i<=n;i++){
			ll ans=1e18;
			for(int j=0;j<M;j++){
				ans=min(ans,a[i][j]);
			}
			printf("%lld\n",ans);
		}
	}
}


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

int main() {
	int A, B, C;
	cin >> A >> B >> C;
	if ((A == 7 && B == 5 && C == 5) || (A == 5 && B == 7 && C == 5) || (A == 5 && B == 5 && C == 7)) {
		cout << "YES" << endl;
	}
	else cout << "NO" << endl;
}

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

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
	#define eprintf(...) 42
#endif

typedef long long int int64;


const int N = (int) 1e5 + 100;
int a[N];


int main(int,  char **)
{
#ifdef LOCAL
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

    int n, l;
    scanf("%d%d", &n, &l);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    int lst = -1;
    for (int i = 0; i < n - 1; i++)
        if (a[i] + a[i + 1] >= l)
            lst = i;

    if (lst == -1)
    {
        printf("Impossible\n");
        return 0;
    }

    printf("Possible\n");
    for (int i = 0; i < lst; i++)
        printf("%d\n", i + 1);
    for (int i = n - 2; i >= lst + 1; i--)
        printf("%d\n", i + 1);
    printf("%d\n", lst + 1);


	return 0;
}




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

#define SORT(x) sort((x).begin(),(x).end())
#define RSORT(x) sort((x).begin(),(x).end(),greater<int>())
#define SZ(x) ((int)(x).size())
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) " (L" << __LINE__ << ") " << __FILE__ << endl;

typedef long long ll;
const int mod = 1e9+7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;

void solve()
{
  int r,g,b,n;
  cin>>r>>g>>b>>n;

  int ans=0;
  for (int i=0; i*r<=n; i++) {
    for (int j=0; i*r+j*g<=n; j++) {
      if ((n-(i*r+j*g))%b == 0) {
        ans++;
      }
    }
  }

  cout << ans << endl;
}

int main()
{
  solve();
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[212345];
ll n, sum, ans;
const ll mod = 1e9 + 7;
int main() {
	cin >> n;
	for (int i = 0; i < n; ++i)cin >> a[i];
	for (int i = 0; i < n; ++i)sum += a[i];
	sum %= mod;
	for (int i = 0; i < n; ++i) {
		sum -= a[i];
		ans += (sum % mod) * a[i];
		ans %= mod;
	}
	if (ans < 0)ans += mod;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 5148
using System;
using System.Linq;
using System.Collections.Generic;
class Program
{
    static void Main(string[] args)
    {
        string[] s = Console.ReadLine().Split(' ');
        int A = int.Parse(s[0]);
        int B = int.Parse(s[1]);
        int X = int.Parse(s[2]);

        Console.WriteLine((A + B >= X && X >= A) ?
            "YES" : "NO");
    }
}


Measured memory_bytes: 13140
// 2011/02/18 Tazoe

#include <iostream>
using namespace std;

int main()
{
	int seg[11][7] = {{0,1,1,1,1,1,1},		// eÌf[^
	                  {0,0,0,0,1,1,0},
	                  {1,0,1,1,0,1,1},
	                  {1,0,0,1,1,1,1},
	                  {1,1,0,0,1,1,0},
	                  {1,1,0,1,1,0,1},
	                  {1,1,1,1,1,0,1},
	                  {0,1,0,0,1,1,1},
	                  {1,1,1,1,1,1,1},
	                  {1,1,0,1,1,1,1},
	                  {0,0,0,0,0,0,0}};		// seg[10]ÍúóÔ

	while(true){
		int n;
		cin >> n;
		if(n==-1)
			break;

		int pst = 10;		// 1ÂOÌiúlÍñ\¦j
		int now;		// »ÝÌ
		for(int i=0; i<n; i++){
			cin >> now;
			for(int j=0; j<7; j++)
				cout << (seg[pst][j]+seg[now][j])%2;		// ¯¶Èç0CÙÈéÈç1
			cout << endl;
			pst = now;
		}
	}

	return 0;
}

Measured memory_bytes: 0
#include "iostream"
#include "vector"
#include "string"
#include "algorithm"
#include "math.h"
#include "cstring"
#include "stack"
#include "queue"
#include "cmath"
#include "set"

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<vector<ll> > mat;

const ll mod = 1e9 + 7;

void decompPrimepair(ll n, vector<pll> &ans)
{
  ll check = 0;
  while (n % 2 == 0)
  {
    check++;
    n /= 2;
  }
  ans.push_back(pll{2, check});

  ll m = sqrt(n);
  ll i = 3;
  while (true)
  {
    if (n == 1)
    {
      break;
    }
    if (i > m)
    {
      ans.push_back(pll{n, 1});
      break;
    }
    if (n % i == 0)
    {
      ll check = 0;
      while (n % i == 0)
      {
        check++;
        n /= i;
      }
      m = sqrt(n);
      ans.push_back(pll{i, check});
    }
    i += 2;
  }
}

ll power_ll_p(ll a, ll b, ll p)	//F_pでのべき
{
  if (b > p)
  {
    b %= (p - 1);//位数p-1
  }
  if (b == 0)
  {
    return 1;
  }
  if (b % 2 == 0)
  {
    ll t = power_ll_p(a, b / 2, p);
    return t * t % p;
  }
  else
  {
    return a * power_ll_p(a, b - 1, p) % p;
  }
}

ll extgcd(ll a, ll b, ll&x, ll&y)
{
  if (b == 0)
  {
    x = 1;
    y = 0;
    return a;
  }
  else
  {
    ll q = a / b;
    ll g = extgcd(b, a - q * b, x, y);
    ll z = x - q * y;
    x = y;
    y = z;
    return g;
  }
}

//modp逆元
ll inversemod(ll a, ll p)
{
  ll x, y;
  extgcd(a, p, x, y);
  x %= p;
  if (x < 0)
  {
    x += p;
  }
  return x;
}

int main()
{
  int n;
  cin >> n;
  ll ans = 0;
  ll a[10010];
  for (int i = 0; i < n; i++)
  {
    cin >> a[i];
    ans += inversemod(a[i], mod);
    ans %= mod;
  }

  sort(a, a + n);
  vector<pll> v(0);
  decompPrimepair(a[0], v);
  for (int i = 1; i < n; i++)
  {
    int size = v.size();
    for (int j = 0; j < size; j++)
    {
      ll check = 0;
      ll p = v[j].first;
      while (a[i] % p == 0)
      {
        check++;
        a[i] /= p;
      }
      v[j].second = max(check, v[j].second);
    }
    vector<pll> u(0);
    decompPrimepair(a[i], u);
    v.insert(v.end(), u.begin(), u.end());
  }

  ll l = 1;
  int size = v.size();
  for (int j = 0; j < size; j++)
  {
    l *= power_ll_p(v[j].first, v[j].second, mod);
    l %= mod;
  }
  ans *= l;
  ans %= mod;
  cout << ans << "\n";
}

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

typedef long long ll;
const int N=100100;
const ll inf=1e18;
ll a[N],f[N],mn,T,L;
int n,q[N];
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>L>>T;
	for(int i=1;i<=n;++i)cin>>a[i],f[i]=i*T;
	mn=inf;
	int t=0,w=0;q[0]=0;
	for(int i=1,j=0;i<=n;++i){
		for(;j<i&&2*(a[i]-a[j+1])>T;++j)mn=min(mn,f[j]-2*a[j+1]);
		f[i]=min(f[i],mn+2*a[i]);
		for(;t<=w&&2*(a[i]-a[q[t]+1])>T;++t);
		if(t<=w)f[i]=min(f[i],f[q[t]]+T);
		for(;t<=w&&f[q[w]]>f[i];--w);
		q[++w]=i;
	}
	cout<<L+f[n]<<'\n';
	return 0;
}


Measured memory_bytes: 2176
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define mfill(x,y) memset(x,y,sizeof(x))
#define all(v) v.begin(), v.end()
#define in(x,y,h,w) if(0<=x&&x<h&&0<=y&&y<w)
#define y0 y12345
#define y1 y54321

#ifdef LOCAL
#define debug(...) fprintf(stderr,__VA_ARGS__)
#else
#define debug(...) 42
#endif

using ul = unsigned long;
using ll = long long;
using P = pair<int, int>;
using vint = vector<int>;using vvint = vector<vector<int>>;
using vll = vector<ll>;using vvll = vector<vector<ll>>;
template<class T>bool chmax(T &a, const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a, const T &b){if(a>b){a=b;return 1;}return 0;}
template <class T>void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
	v.assign(a, vector<T>(b, t));
}
template <class T>T gcd(T &a, T &b){if(a<b){swap(a,b);} T r = a%b; while(r!=0){a=b;b=r;r=a%b;} return b;}

vint dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
vint dx8 = {-1, -1, -1, 0, 1, 1, 1, 0}, dy8 = {-1, 0, 1, 1, 1, 0, -1, -1};

int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);
	debug("debug test\n");
   	int n,m;cin>>n>>m;
	cout << 2*m-n << endl;
	return 0;
}


Measured memory_bytes: 256
#define	_USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <string>
#include <set>
#include <complex>
#include <utility>
#define  rep(i,n) for(int i=0;i<(n);i++)
#define  REP(i,n) for(int i=1;i<(n);i++)
#define  rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define  VI	vector<int>
#define	 VS vector<string>
#define  all(a) (a).begin(),(a).end()
#define  debug(x) cout<<#x<<": "<<x<<endl
using namespace std;
typedef pair<int,int> P;
int main(){
	
	bool p[50001]={false};
	p[2]=true;
	
	for(int i=3;i<=50000;i+=2){
		bool f=false;
		for(int j=3;j<=sqrt(i);j+=2){
			if(i%j==0){
				f=true;
				break;
			}
		}
		if(!f)
			p[i]=true;
	}
	int n;

	while(cin>>n,n!=0){
			int count=0;
		for(int i=2;i<=n;i++){
			for(int j=i;j<=n;j++){
				if(p[i]&&p[j]&&i+j==n){
					count++;
					break;
				}
			}
		}
		cout<<count<<endl;
	}
	
}

Measured memory_bytes: 1216
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
#define era(t) t.erase(unique(be(t)),t.end())
typedef long long ll;
using namespace std;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,num=0;
    cin>>n;
    vector<pair<int ,int> > v;
    int a;
    for(int i=0;i<n;i++){
        cin>>a;
        v.pb(make_pair(a,i));
    }
    sort(be(v));
    for(int i=0;i<n;i++){
        if(abs(v[i].second-i)%2==1){
            num++;
        }
    }
    cout << num/2<<endl;
    return 0;
}


Measured memory_bytes: 1400
#include <bits/stdc++.h> 
using namespace std; 
typedef   long long int ll;
int main () {
    ll n,k;cin>>n>>k;
    ll a[k],b[k],sum=0;
    for (ll i=0;i<k;i++) cin>>a[i];
    for (ll i=1;i<k;i++) {
       b[i-1]=a[i]-a[i-1];
    }
    b[k-1]=n-a[k-1]+a[0];
    sort(b,b+k);
    for (ll i=0;i<k-1;i++) sum+=b[i];
    cout<<sum<<endl;
}

Measured memory_bytes: 3456
#include<bits/stdc++.h>
using namespace std;
vector<pair<long long ,long long > > add[2000000];
vector<pair<long long ,long long > > rem[2000000];

long long dp[2000000];
long long tree[2000000];
long long lazy[2000000];
void lzy(long long  x)
{
    tree[x]+=lazy[x];
    lazy[x*2]+=lazy[x];
    lazy[x*2+1]+=lazy[x];
    lazy[x]=0;
}
void update(long long  x,long long  l,long long  r,long long  s,long long  e,long long v)
{
    lzy(x);
    if (s>r || e<l)return;
    if (l>=s && r<=e)
    {
        lazy[x]=v;
        lzy(x);
        return;
    }
    update(x*2,l,(l+r)/2,s,e,v);
    update(x*2+1,(l+r)/2+1,r,s,e,v);
    tree[x]=max(tree[x*2],tree[x*2+1]);
}
long long query(long long  x,long long  l,long long  r,long long  s,long long  e)
{
    lzy(x);
    if (l>e || r<s)return -1e16;
    if (l>=s && r<=e)return tree[x];
    return max(query(x*2,l,(l+r)/2,s,e),query(x*2+1,(l+r)/2+1,r,s,e));
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    long long  n,m;
    cin>>n>>m;
    for (long long  i=0;i<m;i++)
    {
        long long  l,r,v;
        cin>>l>>r>>v;
        add[l].push_back({l-1,v});
        rem[r].push_back({l-1,-v});
    }
    for (long long  i=1;i<=n;i++)
    {
        for (auto x:add[i])update(1,0,n,0,x.first,x.second);
        dp[i] = query(1,0,n,0,i-1);
        for (auto x:rem[i])update(1,0,n,0,x.first,x.second);
        update(1,0,n,i,i,dp[i]);
    }
    cout<<*(max_element(dp,dp+n+1))<<endl;
}


Measured memory_bytes: 128768
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;
const int Maxn = 1e5;

int N, K;
ll M;
vector<pair<int, int> > t;

int fa[Maxn + 5];
int find(int x) {
	if(x == fa[x]) return x;
	return fa[x] = find(fa[x]);
}

int main() {
#ifdef LOACL
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	scanf("%d %lld %d", &N, &M, &K);
	for(int i = 1; i <= N; i++)
		fa[i] = i;
	for(int i = 1; i <= K; i++) {
		int u, v, typ;
		scanf("%d %d %d", &u, &v, &typ);
		u++, v++;
		if(typ == 0) {
			int fu = find(u), fv = find(v);
			if(fu != fv) fa[fu] = fv;
		} else t.push_back(make_pair(u, v));
	}
	int cnt = 0;
	for(int i = 1; i <= N; i++)
		if(i == find(i)) cnt++;
	ll mx = 1LL * cnt * (cnt - 1) / 2 + N - cnt;
	if(mx < M) {
		puts("No");
		return 0;
	}
	ll mn = (t.empty() ? N - 1 : N);
	if(mn > M) {
		puts("No");
		return 0;
	}
	for(int i = 0; i < (int)t.size(); i++)
		if(find(t[i].first) == find(t[i].second)) {
			puts("No");
			return 0;
		}
	puts("Yes");
	return 0;
}


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

int main() {
	ll n, k;
	cin >> n >> k;
	
	if((n*500) >= k){
	    cout << "Yes" << endl;
	}else{
	    cout << "No" << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define rep(i,n) FOR(i,0,n)
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define vint vector<int>
#define vdouble vector<double>
#define vstring vector<string>
using namespace std;

#include<map>
#include<set>
#include<queue>

typedef long long ll;
typedef unsigned long long ull;

const int MAX_N = 1000000;

#include <iostream>
#include <vector>

int A[MAX_N];
int P[MAX_N];
int L[MAX_N], R[MAX_N];

int main() {

	int N;
    cin >> N;
	rep(i, N){cin >> A[i];}
	rep(i, N){P[A[i]]=i;}

	{
		set<int, greater<int>> st;
		for(int x = 1; x<=N; x++){
			auto a = st.upper_bound(P[x]);
			if(a == st.end()){
			  L[x] = -1;
			}
			else{
			  L[x] = *a;
			}
			st.insert(P[x]);
		}
	}

	{
		set<int> st;
		for(int x = 1; x<=N; x++){
			auto a = st.upper_bound(P[x]);
			if(a == st.end()){
				R[x] = N;
			}
			else{
				R[x] = *a;
			}
			st.insert(P[x]);
		}
	}

    ll ret = 0;
	for(int x = 1; x<=N; x++) {
		// printf("x:%d pos:%d left:%d right:%d v:%d\n", x, P[x], L[x], R[x], x * (P[x]-L[x]) * (R[x]-P[x]));
        ll n = ll(P[x]-L[x]) * ll(R[x]-P[x]);
	    ret +=  x * n;
    }
    cout << ret << endl;

}

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

int main() {
    int n; cin>>n;
    vector<int> b(n-1);
    for(int &x: b) cin>>x;
    vector<int> a(n,b[0]);
    for(int i=0;i<n-1;i++){
        if(a[i]>b[i]) a[i]=b[i];
        a[i+1]=b[i];
    }
    long long ans=0;
    for(int i=0;i<n;i++){
        ans+=a[i];
    }
    cout<<ans<<endl;
}

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

#define rep(a,b) for(int a=0; a<b; ++a)

using ll=long long;

template<typename T>
using vec=vector<T>;

int main(void){
	string s; cin>>s;
	string real,pre,loop; bool r=true,l=false;
	rep(i,s.size()){
		if(s[i]=='.') r=false;
		else if(s[i]=='(') l=true;
		else if(s[i]==')') l=false;
		else{
			if(r) real+=s[i];
			else if(!l) pre+=s[i];
			else loop+=s[i];
		}
	}
	
	string fra1,den1,fra2,den2;
	fra1=real+pre,den1=to_string((int)pow(10,pre.size()));
	if(loop!="") fra2=fra1+loop,den2=to_string(stoi(den1)*(int)pow(10,loop.size()));
	else fra2=fra1,den2=den1;
	
	string fra,den;
	if(fra1!=fra2){
		fra=to_string(stoi(fra2)-stoi(fra1));
		den=to_string(stoi(den2)-stoi(den1));
	}
	else{
		fra=fra1;
		den=den1;
	}
	
	//cout<<real<<" "<<pre<<" "<<loop<<endl;
	//cout<<fra<<"/"<<den<<endl;
	
	if(__gcd(stoi(fra),stoi(den))!=1){
		int g=__gcd(stoi(fra),stoi(den));
		fra=to_string((int)(stoi(fra)/g));
		den=to_string((int)(stoi(den)/g));
	}
	while(fra[0]=='0') fra.erase(fra.begin());
	
	cout<<fra<<"/"<<den<<endl;
}


Measured memory_bytes: 3436
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N=2e4+5;
int h,n;
ll dp[N];
int main()
{
    memset(dp,inf,sizeof(dp));
    dp[0]=0;
    scanf("%d%d",&h,&n);
    for(int i=1;i<=n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        for(int j=0;j<=10000;j++)
            dp[j+a]=min(dp[j+a],dp[j]+b);
    }
    ll ans=1e18;
    for(int i=h;i<=20000;i++)
        ans=min(ans,dp[i]);
    printf("%lld\n",ans);
}


Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;
#define int long long
#define endl '\n'
typedef long long ll;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    char c;
    cin >> c;
    ++c;
    cout << c;
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=2e6+5;
long long a[maxn];
int main()
{
	int n;
	long long t;
	scanf("%d %lld",&n,&t);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	long long x=0;
	for(int i=2;i<=n;i++){
		if(a[i]-a[i-1]<t)
			x=x+a[i]-a[i-1];
		else
			x=x+t;
	}
	x=x+t;
	printf("%lld\n",x);
}

Measured memory_bytes: 1792
import sys

l,r=map(int,input().split())

x=int(r/2019)

if l<=(2019*x) and (2019*x)<=r:
  print("0")
  sys.exit()

m=-1

for i in range(l,r):
  for j in range(i+1,r+1):

    a=(i*j)%2019
    if a==0:
      #print("here")
      print(a)
      sys.exit()

    elif m==-1 or m>a:
      #print(i,j,(i*j)%2019)
      m=a

print(m)

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

#define ll long long

using namespace std;

ll a,b,c,d;
ll r;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>a>>b>>c>>d;
    ll g = __gcd(c,d);
    ll nr;
    if (g==1) nr = c*d;
    else {
        nr=c*d/g;
    }
    
    r=(b-a+1)-(b/d-(a-1)/d+b/c-(a-1)/c-(b/nr-(a-1)/nr));
    cout<<r;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")

#define rep(i,n) for(int i=0;i<n;i++)
const long long MOD = 1000000007;

int main(void){
  int n; cin >> n;
  cout << (n-1)/2 << "\n";
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cstdlib>

using namespace std;
//DP用
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;
}

//a^n mod を計算する関数
long long modpow(long long a,long long n,long long mod) {
    long long res = 1;
    while(n > 0) {
        if(n % 2 == 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

//a^(-1) mod すなわちaの逆元を返す関数
long long modinv(long long a,long long mod) {
    return modpow(a,mod-2,mod);
}

//最大公約数をを返す関数
long long gcd (long long a,long long b) {
    if(a % b == 0) {
        return b;
    }else {
        return (gcd(b,a%b));
    }
}

const long long INF = 1LL << 60;
const long long P = 1000000007;

//nCkを求める関数
long long conbi (long long n,long long k) {
    long long res = 1;
    long long inv;
    for(long long i = n-k+1; i <= n; i++) {
        res *= i;
        res %= P;
    }
    for(long long i = 1; i <= k; i++) {
        inv = modinv(i,P);
        res *= inv;
        res %= P;
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    if(n % 2 == 0) {
        cout << n/2;
    }else {
        cout << n/2+1;
    }
    return 0;
}



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

int main() {
  int N;
  cin >> N;
  
  int sum;
  
  sum = N / (10 * 10 * 10 * 10 * 10 * 10 * 10 * 10)
    + N % (10 * 10 * 10 * 10 * 10 * 10 * 10 * 10) / (10 * 10 * 10 * 10 * 10 * 10 * 10)
    + N % (10 * 10 * 10 * 10 * 10 * 10 * 10 ) / (10 * 10 * 10 * 10 * 10 * 10)
    + N % (10 * 10 * 10 * 10 * 10 * 10) / (10 * 10 * 10 * 10 * 10)
    + N % (10 * 10 * 10 * 10 * 10) / (10 * 10 * 10 * 10)
    + N % (10 * 10 * 10 * 10) / (10 * 10 * 10)
    + N % (10 * 10 * 10) / (10 * 10)
    + N % (10 * 10) / 10
    + N % 10;
  
  if (N % sum == 0) {
    cout << "Yes" << endl;
  }
  
  else {
    cout << "No" << endl;
  }
}




Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
 
long long n,val[100005],w,v,k,mxw,ans;
bool dp[100005]; 
int main(){
	dp[0]=true;
	scanf("%lld%lld",&n,&mxw);
	for (int i=1;i<=n;i++){
		scanf("%lld%lld",&w,&v);
		for (int j=mxw;j>=0;j--){
			if (dp[j]== true && j+w <= mxw){
				dp[j+w]=true;
				val[j+w]=max(val[j+w],val[j]+v);
			}
		}
	}
	ans=0;
	for (int i=mxw;i>=1;i--){
		ans=max(ans,val[i]);
	}
	printf("%lld\n",ans);
	return 0;
} 

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

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin >> s;
    int c = 0;
    for(char ch : s){
        c += (ch - '0');
    }
    cout << (c%9 == 0? "Yes" : "No");
    return 0;
}
 


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

int main() {
  int x,a,b;
  cin>>x>>a>>b;
  if(a>=b){
    cout<<"delicious"<<endl;
  }
  else if(a<b&&b-a<=x){
    cout<<"safe"<<endl;
  }
  else{
    cout<<"dangerous"<<endl;
  }
  
}


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

#define rep(i, n) for(int (i) = 0; i < (n); ++(i))

using ll = long long int;
const ll MOD = 1e9 + 7;

const int MAX_Q = 50;
int N, M, Q;
int A[MAX_Q], a[MAX_Q], b[MAX_Q], c[MAX_Q], d[MAX_Q];

int dfs(int i, int x) {
  A[i] = x;

  if(i == N - 1) {
    int ret = 0;
    rep(t, Q) {
      if(A[b[t]] - A[a[t]] == c[t]) ret += d[t];
    }
    return ret;
  }

  int ret = 0;
  for(int y = x; y <= M; ++y) {
    ret = std::max(ret, dfs(i + 1, y));
  }
  return ret;
}

int main() {
  std::cin >> N >> M >> Q;

  rep(i, Q) {
    std::cin >> a[i] >> b[i] >> c[i] >> d[i];
    --a[i]; --b[i];
  }

  int ans = 0;
  for(int x = 1; x <= M; ++x) {
    ans = std::max(ans, dfs(0, x));
  }

  std::cout << ans << '\n';
}


Measured memory_bytes: 3664
#include<iostream>
#include<vector>
using namespace std;
typedef struct {
	int val,w;
double v;
}knap;
int main(void){
	int n,lw;
	cin>>n>>lw;
vector<int>v(n),w(n);
vector<vector<int> >val(lw+1,vector<int>(n+1,0));
for(int i=0;i<n;i++){
	cin>>v[i]>>w[i];
}

for(int i=0;i<n;i++){
	for(int j=1;j<lw+1;j++){
		if(j>=w[i]){

			val[j][i+1]=max(val[j][i],val[j-w[i]][i+1]+v[i]);
		}else{
			val[j][i+1]=val[j][i];
		}
	}

}
cout<<val[lw][n]<<endl;
	return 0;
}

Measured memory_bytes: 7088
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i < (b); i++)
#define rrep(i, a, b) for (int i = a; i >= (b); i--)
#define all(x) (x).begin(), (x).end()
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;
}
void hr() {
   cerr << "--------------" << endl;
}
const int INF = 1001001001;
const int MOD = 1000000007;
// const int MOD = 998244353;

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

   int a;
   ll b, n;
   cin >> a >> b >> n;
   ll ans = (ll)a * min(n, b - 1) / b;
   cout << ans << endl;
   return 0;
}

Measured memory_bytes: 3572
n = int(input())


def f(x):
    return x * (x + 1) // 2


ans = 0
for x in range(1, n + 1):
    if x * x > n:
        break
    ans += x * x
    y_high = n // x
    ans += 2 * x * (f(y_high) - f(x))
print(ans)


Measured memory_bytes: 9140
import fractions
#import math はpython3.5以降であることに注意

a,b,c,d = map(int, input().split())

#b_minus_a = b-a


#基本方針：bまでの解を求め、その後に(a-1)までの解を差し引く
#　　　　　その残りがこの問題の解

cnt = b - int((b // c)) - int((b // d))

#cとdの最小公倍数を求める
cnt = cnt + (b // int(c*d / fractions.gcd(c,d)))

cnt_a = (a-1) - int( ( (a-1) // c ) ) - int( ( (a-1) // d) )
cnt_a = cnt_a + ((a-1) // int(c*d / fractions.gcd(c,d)))

cnt = cnt - cnt_a


#考え方は正しいが、時間超過
#i = 1
#while( i * d < b_minus_a ):
#  if( i * d % c != 0 ):
#    cnt -= 1
#  
#  i += 1
  
print(cnt)
  

Measured memory_bytes: 5048
import math
n = int(input())

for i in range(n):
    s, t = map(int, input().split())
    a = min(s, t)
    b = max(s, t)
    r = a * b
    q = math.sqrt(r)
    x = int(q)
    if x == q:
        x -= 1

    if a + 1 >= b:
        ans = a * 2 - 2
    elif x * (x + 1) >= a * b:
        ans = x * 2 - 2
    else:
        ans = x * 2 - 1
    print(ans)

Measured memory_bytes: 3064
def main():
    N,M=map(int,input().split())
    L=2**N
    dp=[10**7 for i in range(L)]
    dp[0]=0


    for i in range(M):
        a, _ = map(int, input().split())
        key=sum([2**(int(i)-1) for i in input().split()])
        for j in range(L):
                q=j|key
                dp[q]=min(dp[j]+a,dp[q])


    ans=dp[L-1]
    print(ans if ans<10**7 else -1)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3188
import java.io.*;
public class Main{
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String input = br.readLine();
    String[] param = input.split(" ");
    int time = Integer.parseInt(param[0]);
    int s = time % 60;
    int m = (time / 60) % 60 ;
    int h = (time / 60 / 60) % 60;
    System.out.println(h + ":" + m + ":" + s);
  }
}

Measured memory_bytes: 24316
import java.util.Scanner;

public class Main {

	public static String Y = "Yes";
	public static String N = "No";
	public static String I = "IMPOSSIBLE";
	public static String B = "Bad";
	public static String G = "Good";
	public static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {

		int n = ni();
		int k = ni();
		char[] s = nc();

		for (int i = 0; i < n; i++) {
			if (i == k - 1) {
				outn((char) (s[i] - 'A' + 'a'));

			} else {
				outn(s[i]);
			}
		}

	}

	/*
	 * 以下メソッド集
	 */
	static int ni() {
		return sc.nextInt();
	}

	static long nl() {
		return sc.nextLong();
	}

	static String n() {
		return sc.next();
	}

	static char[] nc() {
		return sc.next().toCharArray();
	}

	static int kaijo(int n) {
		if (n == 0 || n == 1) {
			return 1;
		} else {
			return n * kaijo(n - 1);
		}
	}

	static int fib(int n) {
		return (n == 1 || n == 0) ? n : fib(n - 2) + fib(n - 1);
	}

	static long lcm(long m, long n) {

		return m * n / gcd(m, n);
	}

	static int lcm(int m, int n) {

		return m * n / gcd(m, n);
	}

	static long gcd(long a, long b) {
		return (b == 0) ? a : gcd(b, a % b);
	}

	static int gcd(int a, int b) {
		return (b == 0) ? a : gcd(b, a % b);
	}

	static void out(String info) {
		System.out.println(info);
	}

	static void out(int info) {
		System.out.println(info);
	}

	static void out(double info) {
		System.out.println(info);
	}

	static void out(long info) {
		System.out.println(info);
	}

	static void out(char info) {
		System.out.println(info);
	}

	static void outn(String info) {
		System.out.print(info);
	}

	static void outn(int info) {
		System.out.print(info);
	}

	static void outn(double info) {
		System.out.print(info);
	}

	static void outn(long info) {
		System.out.print(info);
	}

	static void outn(char info) {
		System.out.print(info);
	}
}

Measured memory_bytes: 21844
#include <iostream>
using namespace std;
int main() {
	int i,a,b;
	for (i=1;1;i++) {
		cin>>a>>b;
		if (a==0&&b==0) 
			break;
		if (a<=b)
			cout<<a<<" "<<b<<endl;
		else if (a>=b)
			cout<<b<<" "<<a<<endl;
	}
	return 0;
}


Measured memory_bytes: 3088