akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define f(i,a,n) for(int i=a ; i<n ; i++)
#define inf 1e17
#define MAX_SIZE 1000005 

void pr(int arr[], int size) 
{ for (ll i=0; i < size; i++) {printf("%d ", arr[i]); }cout << endl;}

int main () {
  ll t = 1;
//   cin >> t;
  while(t--){
    string s;
    cin >> s;
    if(s[1] == 'B'){
        cout << "ARC" << endl;
    }
    else{
        cout << "ABC" << endl;
    }
  }
    return 0;
}


Measured memory_bytes: 3612
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <map>

using namespace std;
#define prev prev55

long long n, m;
vector<int> g[500000];

int color[500000];
int bipartite = 1;
int c[3];

void dfs(int v, int fl)
{
    color[v] = fl;
    c[fl]++;
    for (auto u : g[v])
    {
        if (color[u] == fl) bipartite = 0;
        else if (color[u] == 0) dfs(u, 3 - fl);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1, 1);
    if (bipartite)
    {
        cout << c[1] * (n - c[1]) - m;
    }
    else
    {
        cout << n * (n - 1) / 2 - m;
    }
}


Measured memory_bytes: 16384
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <set>
#include <map>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;

struct edge{ll from, to, cost;};
struct graph{
  ll V;
  vector<ll> d;
  vector<edge> es;
  graph(ll n){
    init(n);
  }
  void init(ll n){
    V = n;
    d.resize(V);
    REP(i,V){
      d[i] = INF;
    }
  }
  void add_edge(ll from, ll to, ll cost){
    edge e;
    e.from = from, e.to = to, e.cost = cost;
    es.push_back(e);
  }
  bool bellman_ford(ll s){
    REP(i,V) d[i] = INF;
    d[s] = 0;
    ll cnt = 0;
    while(true){
      bool update = false;
      for(auto e:es){
        if(d[e.from]!=INF&&d[e.to]>d[e.from]+e.cost){
          d[e.to] = d[e.from] + e.cost;
          update = true;
          if(cnt==V-1) return true;
        }
      }
      if(!update) break;
      cnt++;
    }
    return false;
  }
};

int main(){
  ll V,E,r;
  cin >> V >> E >> r;
  graph g(V);
  REP(i,E){
    ll s,t,d;
    cin >> s >> t >> d;
    g.add_edge(s,t,d);
  }
  if(g.bellman_ford(r)){
    cout << "NEGATIVE CYCLE" << endl;
  }else{
    REP(i,V){
      if(g.d[i]==INF){
        cout << "INF" << endl;
      }else{
        cout << g.d[i] << endl;
      }
    }
  }
  return 0;
}



Measured memory_bytes: 3232
#include <iostream>
using namespace std;
typedef long long ll;

int main(){
  ll N;
  cin >> N;
  ll A[N];
  ll B[N] = {};
  for(ll i=0;i<N-1;++i) {
    cin >> A[i];
    ++B[A[i]-1];
  }
  for(ll j=0;j<N;++j) {
    cout << B[j] << endl;
  }
}

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

typedef struct {
	int x;
	int y;
} posn;

posn* next(posn *now, char bord[128][128], int W, int H) {
	posn* ans;

	ans = (posn*)malloc(sizeof(posn));

	ans->x = now->x;
	ans->y = now->y;

	switch(bord[now->y][now->x]) {
		case '>' : if(now->x < W - 1)
					   ans->x = now->x + 1;
				   else
					   ans->x = now->x;
				   break;

		case '<' : if(now->x > 0)
					   ans->x = now->x - 1;
				   else
					   ans->x = now->x;
				   break;

		case 'v' : if(now->y < H - 1)
					   ans->y = now->y + 1;
				   else
					   ans->y = now->y;
				   break;

		case '^' : if(now->y > 0)
					   ans->y = now->y - 1;
				   else
					   ans->y = now->y;
				   break;
	}

	return ans;
}

int main() {
	int W , H;
	char bord[128][128];
	int count = 0;
	posn now;
	posn *temp;

	int i, j;

	while(1) {
		scanf("%d %d", &H, &W);
		if(W == 0 && H == 0)
			break;

		for(i = 0; i < H; i++)
			scanf("%s", bord[i]);

		now.x = 0; now.y = 0;

		count = 0;
		while(count < W * H) {
			temp = next(&now, bord, W, H);

			if(temp->x == now.x && temp->y == now.y)
				break;

			else {
				now.x = temp->x;
				now.y = temp->y;
			}

			count++;
			free(temp);
		}

		if(count == W * H)
			printf("LOOP\n");
		else
			printf("%d %d\n", now.x, now.y);

	}

	return 0;
}

Measured memory_bytes: 632
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#include <math.h>
#include <bitset>
#include <queue>
#include <set>
#include <iomanip>
#include <math.h>
#include <assert.h>
// #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long int INFLL = 1001001001001001LL;
constexpr long long int infll = 1001001001001001LL;
constexpr int INF = 1000000007;
constexpr int inf = 1000000007;
const int mod = 1000000007;

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

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

ll lcm(ll a, ll b)
{
    return a / gcd(a, b) * b;
}

inline double nCr(const int n, int r)
{
    if (n == 0)
    {
        return 0;
    }
    if (r == 0)
    {
        return 1;
    }
    if (r == 1)
    {
        return n;
    }
    if (n == r)
    {
        return 1;
    }

    if (r > n / 2)
    {
        r = n / 2;
    }

    double result = 1;
    for (double i = 1; i <= r; i++)
    {
        result *= (n - i + 1) / i;
    }

    return (result);
}

template <typename T>
T seinomi(T a)
{
    if (a > 0)
    {
        return a;
    }
    else
    {
        return 0;
    }
}

template <typename T>
map<T, T> soinsuubunkai(T n) //連想配列[素因数f.first][個数f.second]
{
    map<T, T> ret;
    for (T i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            ret[i]++;
            n /= i;
        }
    }
    if (n != 1)
        ret[n] = 1;
    return ret;
}

template <typename T>
T ketasuu(T num)
{
    return std::to_string(num).length();
}

int kaizyou(int k)
{
    int sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}

template <class ForwardIt, class T>
void iota(ForwardIt first, ForwardIt last, T value)
{
    while (first != last)
    {
        *first++ = value;
        ++value;
    }
}

//nの階乗を計算
int factorial(int n)
{
    int answer = 1;
    while (n > 1)
    {
        answer *= n;
        n--;
    }
    return answer;
}
int comb(int n, int r)
{
    return factorial(n) / (factorial(r) * factorial(n - r));
}

long long modpow(long long a, long long n, long long mod)
{
    long long res = 1;
    while (n > 0)
    {
        if (n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

//小数点以下10桁テンプレート（main関数内の最初に貼付け）
//std::cout << std::fixed << std::setprecision(10);

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

int main(){
string s;
cin>>s;
bool flag=true;
for(int i=0;i<s.size();i++){
    if(i%2==0){
        if(s.at(i)=='L'){
            flag=false;
        }
    }
    if(i%2>0){
        if(s.at(i)=='R'){
            flag=false;
        }
    }
}
if(flag){
    cout<<"Yes"<<endl;
}else{
    cout<<"No"<<endl;
}
}










Measured memory_bytes: 256
# Author: cr4zjh0bp
# Created: Sat Mar 28 11:53:27 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import defaultdict, deque

n, x, y = na()
x -= 1
y -= 1
d = defaultdict(int)
g = [[] for _ in range(n)]
for i in range(n - 1):
    g[i].append(i + 1)
    g[i + 1].append(i)
g[x].append(y)
g[y].append(x)

def bfs(i):
    q = deque()
    q.append(i)
    dist = [-1] * n
    dist[i] = 0
    while len(q):
        p = q.popleft()
        for j in g[p]:
            if dist[j] != -1:
                continue
            dist[j] = dist[p] + 1
            q.append(j)

    return dist

dic = defaultdict(int)
for i in range(n):
    d = bfs(i)
    for j in range(n):
        dic[d[j]] += 1

for i in range(1, n):
    print(dic[i] // 2)

Measured memory_bytes: 51292
class RMQ:
    inf = 0
    def __init__(self,n_):
        self.n_ = n_
        self.n = 1
        while self.n < n_: self.n*=2
        self.st = [self.inf]*(2*self.n-1)
    
    def update(self,k,x):
        k+=(self.n-1)
        self.st[k] = x
        while k >0:
            k = (k-1)//2
            self.st[k] = max(self.st[2*k+1],self.st[2*k+2])

    def search(self,a,b,k,l,r):
        if r<=a or b<=l :return self.inf
        if a<=l and r<=b:return self.st[k]
        L = self.search(a,b,k*2+1,l,(l+r)//2)
        R = self.search(a,b,k*2+2,(l+r)//2,r)
        return max(L,R)

    def query(self,a,b):
        return self.search(a,b,0,0,self.n)

n = int(input())
x = list(map(int,input().split()))
rmq = RMQ(n+1)
for i in x:
    res = rmq.query(1,i)
    rmq.update(i,i+res)
print (sum(x)-rmq.query(1,n+1))




Measured memory_bytes: 16216
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define vtpl(x,y,z) vector<tuple<x,y,z>>
#define at(x,i) get<i>(x);
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
ll modfac(ll a){
    ll ans=1;
    while(a>1){
        ans*=a;
        ans%=1000000007;
        a--;
    }
    return ans;
}
ll modinv(ll a,ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}
struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) {}

    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};
ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
int main(){
    ll n;cin >> n;
    vl p;
    p.pb(1);
    ll a=1;
    rep(i,6){
        a*=6;
        p.pb(a);
    }
    ll b=1;
    rep(i,5){
        b*=9;
        p.pb(b);
    }
    sort(all(p));
    vl dp(n+1,inf);
    dp[0]=0;
    rep(i,12){
        rep(j,n+1){
            if(j-p[i]>=0)chmin(dp[j],dp[j-p[i]]+1);
        }
    }
    cout <<dp[n] <<endl;
}

Measured memory_bytes: 1024
# -*- coding: utf-8 -*-
"""
Created on Wed Feb 27 01:23:46 2019

@author: yuta
"""

def atoz(s):
    index_a = s.find('A')
    index_z = len(s) - 1 - s[::-1].find('Z')
    x = index_z - index_a + 1
    if x >= 2:
        print(x)

atoz(input())

Measured memory_bytes: 3512
def solve():
    if len(S) < len(T):
        print('UNRESTORABLE')
        return

    valid_strs = []
    for i in range(len(S)):
        for j in range(len(T)):
            if len(S) <= i + j or S[i + j] != '?' and S[i + j] != T[j]:
                break
        else:
            valid_strs.append((S[: i] + T + S[i + len(T): ]).replace('?', 'a'))
    print(min(valid_strs) if valid_strs else 'UNRESTORABLE')

if __name__ == "__main__":
    S = input()
    T = input()
    solve()

Measured memory_bytes: 63260
#include<iostream>
using namespace std;
int main(){
    int n;
    int a[100][100];
    int max = 0;
    cin >> n;
    for(int i = 0;i < n;i++)for(int j = 0;j < n;j++){
        cin >> a[i][j] ;
    }
    max = a[0][0];
    int s = 0;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            
            for(int I = i;I < n ;I++){
                s = 0;
                for(int J = j;J < n;J++){
                    for(int k = i;k < I + 1;k++){
                        s += a[k][J] ;
                        //cout << a[k][J] << endl;
                    } 
                //cout << " i " << i << " j  " << j << " I  " << I << " J  " << J << " s " << s << endl;
                if(s > max)max = s;  
                }
            }
        }
    }
    cout << max <<endl;
}


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

int NextInt() { int d; scanf("%d", &d); return d; }


int comp(const void* a, const void* b) {
  if (*(int*)a > *(int*)b) {
    return 1;
  }
  return 0;
}

int main() {
  int i, n;
  int a[1001];
  int min;

  while (1) {
    n = NextInt();
    if (n == 0) {
      break;
    }
    for (i = 0; i < n; i++) {
      a[i] = NextInt();
    }    
    qsort(a, n, sizeof(a[0]), comp);
    min = 10000001;
    for (i = 1; i < n; i++) {
      if (a[i] - a[i - 1] < min) {
        min = a[i] - a[i - 1];
      }
    }
    printf("%d\n", min);
  }
  return 0;
}

Measured memory_bytes: 652
int main() {
int n, ans = 0;
scanf("%d", &n);
char str[n + 1];
scanf("%s", str);
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
for (int k = 0; k < 10; k++) {
int idx = 0;
for (int l = 0; l < n; l++) {
int pos[] = {i, j, k};
if (str[l] - '0' == pos[idx]) {
idx++;
}
if (idx == 3) {
ans++;
break;
}
}
}
}
}
printf("%d\n", ans);
return 0;
}

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

typedef long long ll;
int N, P;
int odd, even;
vector<ll> po;

int main() {
    po.resize(60);
    po[0] = 1;
    for(int i = 1; i < 60; i++) {
        po[i] = po[i - 1] * 2;
    }

    scanf("%d %d", &N, &P);

    odd = even = 0;
    for(int i = 0; i < N; i++) {
        int t; scanf("%d", &t);
        if(t % 2) odd++;
        else even++;
    }

    if(odd == 0) {
        if(P) printf("0");
        else printf("%lld", po[N]);
    }
    else printf("%lld", po[N - 1]);
}


Measured memory_bytes: 256
// ------------------------------------
// Date:2018/ 3/ 1
// Problem:ABC 059 Three-letterAcronym a.cpp
//
// ------------------------------------

#include <bits/stdc++.h>

using namespace std;

#define EACH(i,a) for (auto&& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define debug(x) cerr << #x << ":" << x << endl

typedef long long ll;

static const int MOD = 1000000007;

int main()
{
  string s1, s2, s3;
  cin >> s1 >> s2 >>s3;
  printf("%c", toupper(s1[0]));
  printf("%c", toupper(s2[0]));
  printf("%c\n", toupper(s3[0]));
  return 0;
}



Measured memory_bytes: 256
import sys
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
sys.setrecursionlimit(int(1e+6))
MOD = int(1e+9) + 7
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3

def main():
    A, B = i2nn()
    K = (A + B) // 2
    K2 = (A + B) / 2
    if K == K2:
        print(K)
    else:
        print('IMPOSSIBLE')

main()


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

struct Benri { Benri() { std::cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(12);}} benri;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vll = vector<long long>;
using pll = pair<ll, ll>;
using ull = unsigned long long;

template <typename T> using PQ = priority_queue<T>;
template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define F first
#define S second

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

//constexpr long long MOD = 1000000007;
constexpr long long MOD = 998244353;
constexpr double EPS = 1e-10;
constexpr int INF = 1001001001;
//constexpr ll INF = 1001001001001001001ll;

using number = long long;


constexpr ll N_MAX = 200000;
constexpr ll A_MAX = 1000001;

number fac[A_MAX], finv[A_MAX], inv[A_MAX];
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < A_MAX; i++) {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
vll w(A_MAX);

inline void init_w() {
    COMinit();
    for (int i = 1; i < A_MAX; ++i) {
        w[i] = inv[i];
    }
    for (int i = 1; i < A_MAX; ++i) {
        for (int j = i + i; j <= A_MAX; j += i) {
            w[j] += MOD - w[i];
            w[j] %= MOD;
        }
    }
}

int main() {
    init_w();
    int n; cin >> n;

    vll a(A_MAX, 0);
    ll aa;
    for (int i = 0; i < n; ++i) {
        cin >> aa;
        ++a[aa];
    }

    ll ans = 0;
    for (int i = 1; i < A_MAX; ++i) {
        ll s = 0, t = 0;
        for (int j = i; j < A_MAX; j += i) {
            s += (j * a[j]) % MOD;
            s %= MOD;
            t += ((j * a[j]) % MOD * j) % MOD;
            t %= MOD;
        }
        ans += (w[i] * (((s * s) % MOD - t + MOD) % MOD)) % MOD;
        ans %= MOD;
    }

    cout << (ans * inv[2]) % MOD << endl;
}

Measured memory_bytes: 39296
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

typedef pair<ll, ll> P;
#define fs first
#define sc second

int main(){
    string s, t;
    cin >> s >> t;
    int a, b;
    cin >> a >> b;
    string u;
    cin >> u;

    if(s == u) a--;
    if(t == u) b--;

    cout << a << " " << b << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define st first
#define nd second
#define turbo ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define vi vector<int>
#define vvi vector<vi>
#define qi queue<int>
#define ld long double

using namespace std;

/*---------------------------------------------------------///CODE///---------------------------------------------------------*/

const int N = 1e5;

ll dp[101][N + 10];
int weight[N + 10];
ll value[N + 10];

int main()
{
    turbo

    int n, w; cin >> n >> w;

    for(int i = 1; i <= n; i++)
        cin >> weight[i] >> value[i];

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= w; j++)
            if(weight[i] <= j)
                dp[i][j] = max(dp[i - 1][j - weight[i]] + value[i], dp[i - 1][j]);
            else
                dp[i][j] = dp[i - 1][j];

    return cout << dp[n][w], 0;
}

Measured memory_bytes: 78464
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <algorithm>
using namespace std;

typedef unsigned int uint;
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vint;
typedef vector<uint> vuint;
typedef vector<ull> vull;
typedef vector<ll> vll;

#define init(type,var) type var;cin>>var;
#define vinit(type,var,n) vector<type> var((uint)n);loop(i,0,n)cin>>var[i];
#define linit(type,var,n) list<type> var;loop(i,0,n){type _v;cin>>_v;var.push_back(_v);}
#define range(container) container.begin(),container.end()
#define loop(i,first,end) for(ull i=(first);i<(end);i++)
#define outl(out) cout<<(out)<<endl;

const ull INF = (ull)(-1LL);

typedef ull aint;

typedef vector<aint> vaint;
typedef list<aint> laint;

int main(void){
	init(aint, n);

	outl(n/2+n%2);

	return 0;
}

Measured memory_bytes: 256
N, Q = map(int, input().split())

l = [[] for i in range(N)]

for i in range(N-1):
  a, b = map(int, input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)

used = [False] * N
r = [0] * N

for i in range(Q):
  p, x = map(int, input().split())
  r[p-1] += x

stack = [0]
while stack:
  i = stack.pop()
  used[i] = True
  for to in l[i]:
    if not used[to]:
      stack.append(to)
      r[to] += r[i]

print(*r)


Measured memory_bytes: 55856
#include<stdio.h>
#include<string.h>
int main()
{
  int m;
  scanf("%d",&m);
  int k;
  char s[100];
  int n;
  char ss[1000][100];
  int count;
  int ans;
  int i,j;
  char f;
  for(k=0;k<m;k++)
  {
    scanf("%s",s);
    n=strlen(s);
    count=0;
    for(i=0;i<n-1;i++)
    {
      for(j=0;j<=i;j++)
        ss[count][j]=s[j];
      for(j=i+1;j<n;j++)
        ss[count][j]=s[j];
      ss[count][n]='\0';
      count++;
      for(j=0;j<=i;j++)
        ss[count][j]=s[j];
      for(j=i+1;j<n;j++)
        ss[count][j]=s[n-j+i];
      ss[count][n]='\0';
      count++;
      for(j=0;j<=i;j++)
        ss[count][j]=s[i-j];
      for(j=i+1;j<n;j++)
        ss[count][j]=s[j];
      ss[count][n]='\0';
      count++;
      for(j=0;j<=i;j++)
        ss[count][j]=s[i-j];
      for(j=i+1;j<n;j++)
        ss[count][j]=s[n-j+i];
      ss[count][n]='\0';
      count++;
      for(j=i+1;j<n;j++)
        ss[count][j-i-1]=s[j];
      for(j=0;j<=i;j++)
        ss[count][j+n-i-1]=s[j];
      ss[count][n]='\0';
      count++;
      for(j=i+1;j<n;j++)
        ss[count][j-i-1]=s[n-j+i];
      for(j=0;j<=i;j++)
        ss[count][j+n-i-1]=s[j];
      ss[count][n]='\0';
      count++;
      for(j=i+1;j<n;j++)
        ss[count][j-i-1]=s[j];
      for(j=0;j<=i;j++)
        ss[count][j+n-i-1]=s[i-j];
      ss[count][n]='\0';
      count++;
      for(j=i+1;j<n;j++)
        ss[count][j-i-1]=s[n-j+i];
      for(j=0;j<=i;j++)
        ss[count][j+n-i-1]=s[i-j];
      ss[count][n]='\0';
      count++;
    }
    for(i=0;i<count-1;i++)
    {
      if(strcmp(ss[i],ss[i+1])>0)
      {
        for(j=0;j<n;j++)
        {
          f=ss[i][j];
          ss[i][j]=ss[i+1][j];
          ss[i+1][j]=f;
        }
        if(i>0)
          i-=2;
      }
    }
    ans=count;
    for(i=1;i<count;i++)
      if(strcmp(ss[i],ss[i-1])==0)
        ans--;
    printf("%d\n",ans);
  }
  return 0;
}


Measured memory_bytes: 2036
#include <bits/stdc++.h>
 
using namespace std;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long int
#define pb push_back
#define MOD 1000000007
#define ull unsigned long long
#define all(x) (x).begin(), (x).end()
#define read(a, n) for(ll i = 0;i<n;i++) cin>>a[i];
#define debug1(x) cout<<#x<<" "<<x<<endl;
#define debug2(x,y) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<endl;
#define debug3(x,y,z) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<" "<<#z<<" "<<z<<endl;
#define FileIO freopen("input.txt","r",stdin);freopen("output.txt","w",stdout)
const int INF = 1e9 + 5;

void solve() {
	ll d, t, s;
	cin>>d>>t>>s;
	
	if(s*t >= d) {
		cout<<"Yes\n";
	}
	else cout<<"No\n";
}

int main()
{
	fastio;
	
	int T = 1;
	//cin>>T;
	//int tc = 1; 
	while(T--) {
		//cout<<"Case #"<<tc<<": ";
		solve();
		//tc++;
	}	
	return 0;
}


Measured memory_bytes: 3608
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int ac = 0,wa = 0,tle = 0,re = 0;
        while(sc.hasNext()){
            String s = sc.next();
            if(s.equals("AC")){
                ac++;
            }
            if(s.equals("WA")){
                wa++;
            }
            if(s.equals("TLE")){
                tle++;
            }
            if(s.equals("RE")){
                re++;
            }
        }
        System.out.println("AC x " + ac);
        System.out.println("WA x " + wa);
        System.out.println("TLE x " + tle);
        System.out.println("RE x " + re);
    }
}


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

vector<int>s;
bool use[1111111];

void MAKE(){
  use[0]=use[1]=1;
  for(int i=2;i<1111111;i++){
    if(!use[i]){
      for(int j=i+i;j<1111111;j+=i) use[j]=1;
    }
  }
  r(i,1111111) if(!use[i]) s.push_back(i);
}

int get(int a,int b){
  int l=-1,r=1e13;
  while(r-l>1){
    int mid=(l+r)/2;
    if(mid*a>=b) r=mid;
    else l=mid;
  }
  return r;
}

int sum[1000009],A[1000009];

signed main(){
  MAKE();
  int l,r;
  cin>>l>>r;
  r(i,r-l+1)A[i]=i+l;
  for(int i=0;i<s.size();i++){
    int N=get(s[i],l);
    N*=s[i];//if(i<=10)cout<<N<<endl;
    while(N<=r){
      while(A[N-l]%s[i]==0){
        sum[N-l]++;
        A[N-l]/=s[i];
      }
      N+=s[i];
    }
  }
  int ans=0;
  r(i,r-l+1){
    if(1<A[i])sum[i]++;
    if(!use[sum[i]]) ans++;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 20504
#define __USE_MINGW_ANSI_STDIO
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_set>
#include <unordered_map>

using namespace std;

typedef long long ll;
typedef long long ull;
typedef pair<int, int> ii;

#define all(v)		((v).begin()), ((v).end())
#define sz(v)		((int)((v).size()))
#define endl		"\n"
#define fx(n)		fixed<<setprecision(n)
#define mk			make_pair	

void fast()
{
	ios::sync_with_stdio(NULL);
	cout.tie(NULL);
	cin.tie(NULL);
/*#ifndef ONLINE_JUDGE
	freopen("output.txt", "w", stdout);
	freopen("input.txt", "r", stdin);
#endif
#ifdef ONLINE_JUDGE
	freopen("output.txt", "w", stdout);
	freopen("pyramid.in", "r", stdin);
#endif*/
}
const double pi = 2 * acos(0.0);
const ll oo = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int nn = 1e6 + 15;
int dx[8] = { -1, 0, 0, 1, 1, -1, 1, -1 };
int dy[8] = { 0, -1, 1, 0, 1, -1, -1, 1 };

int main()
{
	fast();
	int arr[3];
	for (int i = 0; i < 3; i++)
		cin >> arr[i];
	sort(arr, arr + 3);
	if (arr[0] == 5 && arr[1] == 5 && arr[2] == 7)
		cout << "YES\n";
	else
		cout << "NO\n";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define el '\n'
using namespace std;

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

  int n, k;
  cin >> n >> k;
  vector<int> h(n);
  for(int i = 0; i < n; i++){
    cin >> h[i];
  }
  vector<int> dp(n, INT_MAX);
  dp[0] = 0;
  for(int i = 0; i < n; i++){
    for(int j = i+1; j <= i+k && j < n; j++){
      dp[j] = min(dp[j], dp[i]+abs(h[i]-h[j]));
    }
  }
  cout << dp[n-1] << el;
  
  return 0;
}

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

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

using namespace std;

bool calcEug(vector<int> point1, vector<int> point2, int D){
    long long total=0;
    rep(i,D){
        total+=(point1[i]-point2[i])*(point1[i]-point2[i]);
    }
    // cout << sqrt(total) << endl;
    return floor(sqrt(total))*floor(sqrt(total))==total;
}
int main() {
    int N;
    int D;
    cin >> N >> D;
    vector<vector<int> > points(N, vector<int>(D));
    int count = 0;
    rep(i,N){
        rep(j,D){
            cin >> points[i][j];
        }
        if(i!=0){
            for(int k=i-1;k>=0;k--){
                if(calcEug(points[i],points[k],D)) count++;
            }
        }
    }

    cout << count << endl;

}


Measured memory_bytes: 256
N = int(input())
ls = sorted([[int(i) for i in input().split()] for _ in range(N)], key=lambda x:x[1])

total = 0
tf = True
for l in ls:
    total += l[0]
    if total > l[1]:
        tf = False
        break
if tf:
    print('Yes')
else:
    print('No')



Measured memory_bytes: 44888
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
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 main():
    N = I()

    def f(x,y):
        return max(len(str(x)), len(str(y)) )

    ans = inf
    for i in range(1,int(sqrt(N)+1)):
        if N%i==0:
            ans = min(ans, f(i, N//i))
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 6608
#include <algorithm>
#include <iostream>
#include <vector>
#include <utility>
#include <tuple>
#include <cstdint>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <cctype>
#include <cstring>

using namespace std;

typedef long long    ll;
typedef long double  ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;

template <typename T> bool chmax(T &a, T& b) {if (a < b) {a = b; return true;} return false;}
template <typename T> bool chmin(T &a, T& b) {if (a > b) {a = b; return true;} return false;}
#define rep(i, n)      for (int i = 0; i < (int)(n); ++i)
#define rep3(i, m, n)  for (int i = (m); i < (int)(n); ++i)
#define rrep(i, n)     for (int i = (int)(n)-1; i >= 0; --i)
#define rrep3(i, m, n) for (int i = (int)(n)-1; i >= (m); --i)
#define all(x) x.begin(), x.end()
#define rall(x) x.end(), x.begin()
#define mset(x, val) memset(x,(val),sizeof(x))
#define cons(a, b) make_pair((a), (b))
#define car first
#define cdr second

#define endl '\n'
#define INF  0x7f7f7f7f7f7f7f7f
#define INFi 0x7f7f7f7f


ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

ll solve(int N, const vector<ll> & a) {
  return *max_element(all(a)) - *min_element(all(a));
}

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

  int N;
  cin >> N;
  vector<ll> a(N);
  rep (i, N) {
    cin >> a[i];
  }

  auto ans = solve(N, a);
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3164
p = []
for n in range(2, 100000):
    isP = True
    for m in p:
        if m ** 2 > n:
            break
        if n % m == 0:
            isP = False
            break
    if isP:
        p.append(n)

p = set(p)

s = {-1: 0}
for n in range(1, 100000, 2):
    s[n] = s[n - 2]
    if n in p and (n + 1) / 2 in p:
        s[n] += 1

Q = int(input())

for i in range(Q):
    l, r = map(int, input().split())
    print(s[r] - s[l - 2])

Measured memory_bytes: 9916
n, m, l = map(int,input().split())
A=[]
B=[]
ans=[[] for i in range(n)]
for i in range(n):
    A.append(list(map(int,input().split())))
for i in range(m):
    B.append(list(map(int, input().split())))
for i in range(n):
    for k in range(l):
        temp=0
        for j in range(m):
            temp+=A[i][j]*B[j][k]
        ans[i].append(temp)
[print(" ".join(map(str, x))) for x in ans]

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

using namespace std;

int main(){
    char s[10]; scanf("%s", s);
    if(s[0]==s[1]) cout << "Bad" << endl;
    else if(s[1]==s[2]) cout << "Bad" << endl;
    else if(s[2]==s[3]) cout << "Bad" << endl;
    else cout << "Good" << endl;
}

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

using namespace std;
typedef long long ll;

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) x.begin(),x.end() //sortなどの引数を省略したい
#define SIZE(x) ll(x.size()) //sizeをsize_tからllに直しておく
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB emplace_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素
#define Umap unordered_map
#define Uset unordered_set

int main(){
    ll n;
    cin >> n;
    vector<ll> a(n+1), b(n);
    REP(i, n+1) cin >> a[i];
    REP(i, n) cin >> b[i];
    ll ans = 0;
    REP(i, n){
        ans += min(a[i], b[i]);
        ans += max(ll(0), min(a[i+1], b[i] - a[i]));
        a[i+1] -= max(ll(0), min(a[i+1], b[i] - a[i]));
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 4728
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

#define REVERSE(c) (char)(c == 'S' ? 'W' : 'S')
#define NEXT(a, b, c) (char)(a == 'S' ? (b == 'o' ? c : REVERSE(c)) \
                                      : (b == 'o' ? REVERSE(c) : c))
#define CHECK(a, b, c, d) (a == 'S' ? (b == 'o' ? c == d : c != d) \
                                    : (b == 'o' ? c != d : c == d))

int main() {
        int n;
        string s, ans;
        bool flag;
        string pre[4] = {"SS", "SW", "WS", "WW"};
        cin >> n >> s;

        for (int i = 0; i < 4; i++) {
                ans = pre[i];
                for (int j = 1; j < n-1; j++) {
                        ans += NEXT(ans[j], s[j], ans[j-1]);
                }
                flag = true;
                for (int j = 0; j < n; j++) {
                        int next = (j + n + 1) % n;
                        int prev = (j + n - 1) % n;
                        if (CHECK(ans[j], s[j], ans[prev], ans[next]) == 0) {
                                flag = false;
                                break;
                        }
                }
                if (flag == true)
                        break;
        }
        if (flag == true)
                cout << ans << endl;
        else
                cout << -1 << endl;
        return 0;
}


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

#define stirng string
#define vvi vector<vector<int>>
#define vi vector<int>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;

const int inf = 1e9 + 7;

int main() {
  int n;
  cin >> n;
  char t[2 * n];
  string s;
  set<string> set;
  for (int i = 0; i < n; i++) {
    cin >> s;
    set.insert(s);
    t[2 * i] = s[0];
    t[2 * i + 1] = s[s.size() - 1];
  }
  t[0] = '*';
  t[2 * n - 1] = '*';
//  cout << set.size() << endl;
//  for (int i = 0; i < 2 * n; i++) {
//    cout << t[i];
//  }
//  cout << endl;

  if (set.size() != n) {
    cout << "No" << endl;
    return 0;
  } else {
    for (int i = 0; i < n; i++) {
      if (i == 0) {
      } else if (t[2 * i - 1] != t[2 * i]) {
        cout << "No" << endl;
        return 0;
      }
    }
  }
  cout << "Yes" << endl;
  return 0;
}
 

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> ii;
typedef pair<ii,ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
#define getbit(n,i) (((n)&(1<<(i)))!=0)
#define setbit0(n,i) ((n)&(~(1<<(i))))
#define setbit1(n,i) ((n)|(1<<(i)))
#define togglebit(n,i) ((n)^(1<<(i)))
#define lastone(n) ((n)&(-(n)))
#define read freopen("debug\\in.txt","r",stdin)
#define write freopen("debug\\out.txt","w",stdout)
#define fi first
#define se second
#define getI(a) scanf("%d",&a)
#define getII(a,b) scanf("%d%d",&a,&b)
#define PI (acos(-1))
#define fastread ios_base::sync_with_stdio(false);cin.tie(NULL)
#define MOD (1000000007)
#define asz 500005
#define pb push_back
#define ppf pop_front
#define ppb pop_back
#define pf push_front
ll fre[500005];
ll a[500005];

int main(){
    fastread;
     ll n,i,j,k,l,m;
     cin>>n;
     for(i=1;i<=n;i++){
         cin>>a[i];
         fre[a[i]]++;
     }
     ll sum=0;
     for(i=1;i<=n;i++){
         sum+=((fre[i])*(fre[i]-1))/2;
     }
     ///cout<<sum<<endl;
     for(i=1;i<=n;i++){
         ll kola=((fre[a[i]])*(fre[a[i]]-1))/2;
         ///cout<<kola<<endl;
         ll res=sum-kola;
         res+=((fre[a[i]]-1)*(fre[a[i]]-2))/2;
         cout<<res<<"\n";
     }
    return 0;
}

Measured memory_bytes: 8320
#include <bits/stdc++.h>
#define ll long long
#define rw freopen("input.txt","r",stdin),freopen("output.txt","w",stdout);
#define pb push_back
#define F first
#define S second
#define pf push_front
#define lp(i,a,b) for (int i=a;i<=(int)b;++i)
#define lp2(i,a,b) for (int i=a;i>=b;--i)
#define f(x) return cout<<x<<"\n",0
#define pii pair<int,int>
#define pll pair<ll,ll>
#define all(c) c.begin(),c.end()
#define allr(c) c.rbegin(),c.rend()
#define p(x) cout<<#x<<" = { "<<x<<" } \n"
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define EPS 1e-6
// to convert string to number use int a = stoi(string);
// to convert number to string use string s = to_string(int);
#define FAST ios::sync_with_stdio(0),ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define clr(c,x) memset(c,x,sizeof(c));
using namespace std;
const int N=2e5+5,mod=(int)1e9+7;
int main()
{
#ifdef ONLINE_JUDGE
    FAST;
#endif
    int n;
    pll p;
    cin>>n>>p.F>>p.S;
    ll g=__gcd(p.F,p.S);
    p.F/=g;
    p.S/=g;
    ll sum=p.F+p.S;
    n--;
    while(n--)
    {
        ll a,b;
        cin>>a>>b;
        g=__gcd(a,b);
        a/=g;
        b/=g;
        ll r1=(p.F+a-1)/a;
        ll r2=(p.S+b-1)/b;
        ll mx=max(r1,r2);
        a*=mx;
        b*=mx;
        sum=a+b;
        p={a,b};
    }
    f(sum);
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
typedef long long ll;
const int mod=998244353;
char s[200050];
bool a[200050],b[200050];
int n,ans=0,tmp[200050],res[200050];
inline bool cmp(){
	for(int i=1;i<=n;++i)if(a[i]!=b[i])return a[i]<b[i];
	return 1;
}
int main(){
	int i,j,k;
	scanf("%d%s",&n,s+1);
	for(i=1;i<=n;++i){
		b[i]=s[i]=='1';
		tmp[i]=((tmp[i-1]<<1)+b[i])%mod;
	}
	ans=(ll)(tmp[n]+1)*n*2%mod;
	for(k=1;k<=n/3;++k)if(!(n%k)&&n/k%2==1){
		res[k]=tmp[k];
		for(i=1;i<=k;++i)a[i]=b[i];
		for(;i<=n;i+=k)
			for(j=0;j<k;++j)a[i+j]=a[i+j-k]^1;
		if(cmp())res[k]=(res[k]+1)%mod;
		if(k>1)for(i=1;i*i<=k;++i)if(!(k%i)){
			res[k]=(res[k]-res[i]+mod)%mod;
			if(i*i!=k&&i!=1)res[k]=(res[k]-res[k/i]+mod)%mod;
		} 
		ans=(ans-(ll)res[k]*(n-k<<1)%mod+mod)%mod;
	}
	printf("%d\n",ans);
	return 0;
}

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

typedef long long ll;
typedef long double ld;

using namespace std;

void INeedIt() {
	ios_base::sync_with_stdio(0);
    cin.tie(0);		
    cout.tie(0);
}
int a[10];
int main() {
	INeedIt();
	cin>>a[0]>>a[1]>>a[2];
	sort(a, a+3);
	if (a[0]==5 && a[1]==5 && a[2]==7) {
		cout<<"YES";
	}
	else cout<<"NO";
	return 0;
}

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

typedef long long ll;
ll mod = 1000000007;
int arr[1001][1001];
int h, w;
int main(){
    cin >> h >> w;
    char char_c;
    for(int i=1; i<=h; i++){
        for(int j=1; j<=w; j++){
            cin >> char_c;
            if(char_c == '.') arr[i][j] = 1;
            else arr[i][j] = 0;
        }
    }
    ll dp[1001][1001];
    memset(dp, 0, sizeof(dp));
    dp[1][1] = 1;
    for(int i=1; i<=h; i++){
        for(int j=1; j<=w; j++){
            //if(i == 0 || j == 0) dp[i][j] = 0;
            if(i == 1 && j == 1) continue;
            //dp[i][j] = 0;
            if(arr[i][j]){
                if(i > 1) dp[i][j] += dp[i-1][j];
                if(j > 1) dp[i][j] += dp[i][j-1];
                dp[i][j] %= mod;
            }
            //else arr[i][j] = 0;
        }
    }
    cout << dp[h][w] % mod << endl;
}

Measured memory_bytes: 12032
// #pragma GCC target("avx")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
#include<unordered_set>
#include<complex>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3100000;
const int UF_SIZE = 210000;
namespace{
	long long fact[C_SIZE];
	long long finv[C_SIZE];
	long long inv[C_SIZE];
	long long Comb(int a,int b){
	 	if(a<b||b<0)return 0;
	 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
	}
	void init_C(int n){
		fact[0]=finv[0]=inv[1]=1;
		for(int i=2;i<n;i++){
			inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
		}
		for(int i=1;i<n;i++){
			fact[i]=fact[i-1]*i%mod;
			finv[i]=finv[i-1]*inv[i]%mod;
		}
	}
	long long pw(long long a,long long b){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%mod;
			a=a*a%mod;
			b/=2;
		}
		return ret;
	}
	long long pw_mod(long long a,long long b,long long M){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%M;
			a=a*a%M;
			b/=2;
		}
		return ret;
	}
	int pw_mod_int(int a,int b,int M){
		if(a<0)return 0;
		if(b<0)return 0;
		int ret=1;
		while(b){
			if(b%2)ret=(long long)ret*a%M;
			a=(long long)a*a%M;
			b/=2;
		}
		return ret;
	}
	int ABS(int a){return max(a,-a);}
	long long ABS(long long a){return max(a,-a);}
	double ABS(double a){return max(a,-a);}
	int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
	int UF[UF_SIZE];
	void init_UF(int n){
		for(int i=0;i<n;i++)UF[i]=-1;
	}
	int FIND(int a){
		if(UF[a]<0)return a;
		return UF[a]=FIND(UF[a]);
	}
	void UNION(int a,int b){
		a=FIND(a);b=FIND(b);if(a==b)return;
		if(UF[a]>UF[b])swap(a,b);
		UF[a]+=UF[b];UF[b]=a;
	}
}
// ここから編集しろ
int x[10];
int y[10];
int main(){
	int a;scanf("%d",&a);
	double ret=0;
	for(int i=0;i<a;i++){
		scanf("%d%d",x+i,y+i);
	}
	for(int i=0;i<a;i++){
		for(int j=i+1;j<a;j++){
			ret+=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
		}
	}
	printf("%.12f\n",ret/(a*(a-1)/2)*(a-1));
}

Measured memory_bytes: 128
#include<stdio.h>
int sort(int *,int *);
int main(void){
  int n,k;
  scanf("%d%d",&n,&k);
  int h[n+1];
  if(k>=n){printf("0");
           return 0;
          }
  for(int i=0;i<n;i++){
	scanf("%d",&h[i]);
  }
  qsort(h,n,sizeof(int),sort);
  long sum=0;
  for(int i=k;i<n;i++){
    sum+=(long)h[i];
  }
  printf("%ld",sum);
  
  return 0;
}
int sort(int *a,int *b){
  return *b-*a;
}
  
  

Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define mod 1000000007
#define inf 1000000000000000
#define autoit(x,it) for(auto it = x.begin(); it != x.end(); it++)
#define rep(n) for(ll i = 0; i < n; i++)
#define repi(i,n) for(ll i = 0; i < n; i++)

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 

#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 

using namespace std;


int main()
{
   FAST/**/
   
   ll a,b;
   cin>>a>>b;
   
   ll s1 = 0, s2 = 0;
   rep(b)
        s1 = 10*s1 + a;
   rep(a)
        s2 = 10*s2 + b;
  
   cout<<max(s1,s2);        
        
   
   return 0;        
}  
   

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <deque>
#include <stack>
#include <map>
const int MOD = 1e9+7;
const int MOOD = 998244353;
#define PI 3.14159265359
typedef long long ll;
using namespace std;

ll coun[100001];

int main(){
	int n;
	cin >> n;
	for (int i = 0; i < n; i++){
		int x;
		cin >> x;
		coun[x]++;
	}
	int q;
	cin >> q;
	ll ans = 0;
	for (int j = 1; j <= 100000; j++){
		ans += coun[j]*j;
	}
	for (int i = 0; i < q; i++){
		int b, c;
		cin >> b >> c;
		ans -= b*coun[b];
		ans += c*coun[b];
		coun[c] += coun[b];
		coun[b] = 0;
		cout << ans << endl;
	}
}



Measured memory_bytes: 4344
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <set>
#include <climits>
#include <queue>
#include <map>
#include <cmath>
#include <sstream>
#include <bitset>
using namespace std;
typedef long long int ll;
#define MAX_V 16
int adjMat[MAX_V][MAX_V];
bool visited[MAX_V][1<<MAX_V];//visited存的並非節點是否有訪問過,而是這個?態是否有出現過
int dp[MAX_V][1<<MAX_V];//DP表格,第一個中括號代表目前所在的點
//第二個中括號代表目前節點的?態(ex:0101011,表示1,3,5節點還沒走過,可以直接用bitwise操作來判斷?態)
//因為DP表格是N*2^N次方,所以時間複雜度就是O(N*2^N)
int v,e;

const char *byte_to_binary(int x)
{
    static char b[9];
    b[0] = '\0';

    int z;
    for (z = 128; z > 0; z >>= 1)
    {
        strcat(b, ((x & z) == z) ? "1" : "0");
    }

    return b;
}
int TSP(int at,int state)
{
    // printf("at=%d,state=%s\n",at, byte_to_binary(state));
    if(state == (1<<v)-1 && at==0){ //全部的?態都走完而且回到起點惹
        visited[at][state]=true;
        return dp[at][state];
    }
    if(dp[at][state]) //出現過的?態,直接回傳結果
        return dp[at][state];
    int ans = INT_MAX>>1;
    int cost;
    for(int i=0;i<v;i++){
        //state&(1<<i)==0表示判斷右邊數過來第i個bit是否為0,用來判斷該節點是否有走過
        //state|(1<<i)表示將該節點設成走過
        if(adjMat[at][i]!=-1 && (state & (1<<i))==0){
            // printf("at=%d->i=%d\n",at,i);
            cost = TSP(i,state|(1<<i)) + adjMat[at][i];//往?種可以走的路線都走下去
            // printf("at=%d->i=%d,cost=%d\n",at,i,cost);
            ans = min(ans,cost);//求出最小?
        }
    }
    return dp[at][state] = ans;
}
//
int main()
{   
    // freopen("in","r",stdin);
    while(~scanf("%d %d",&v,&e)){
        memset(adjMat,-1,sizeof(adjMat));
        for(int i=0;i<e;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            adjMat[u][v]=w;
        }
        memset(dp,0,sizeof(dp));
        memset(visited,0,sizeof(visited));
        int ans = TSP(0,0);
        if(ans>=INT_MAX>>1)
            puts("-1");
        else
            printf("%d\n",ans);
    }
    return 0;
}

Measured memory_bytes: 6304
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0; i<(n); i++)
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
int main(){
    ll a,b,c,x,y; cin>>a>>b>>c>>x>>y;
    ll res=a*x+b*y;
    if(x>y) chmin(res, c*2*y+a*(x-y));
    else chmin(res, c*2*x+b*(y-x));
    chmin(res, c*2*max(x,y));
    cout<<res<<endl;
    return 0;
}

Measured memory_bytes: 256