akhauriyash/Code-Regression huggingface dataset:
from collections import deque

ans = []
while True:
  w,h = map(int,input().split())
  if w==h==0: 
    # for a in ans:
    #   print(a)
    exit()

  maze = []
  for k in range(h):
    # [(lower, right)]
    row = [ [0,0] for _ in range(w) ]
    
    for i in range(2):
      if i==0:
        # check for right boundary
        v = list(map(int,input().split()))
        for j in range(w-1):
          if v[j] == 1:
            row[j][1] = 1
      else:
        # check for lower boundary
        if k == h-1: continue
        v = list(map(int,input().split()))
        for j in range(w):
          if v[j] == 1:
            row[j][0] = 1

    maze.append(row)

  dist = [ [-1]*w for _ in range(h) ]
  dist[0][0] = 1
  q = deque([(0,0)])

  while q:
    r,c = q.popleft()

    directions = []

    # lower
    if maze[r][c][0] == 0:
      directions.append((1,0))

    # right
    if maze[r][c][1] == 0:
      directions.append((0,1))

    # upper
    if r-1>=0 and maze[r-1][c][0] == 0:
      directions.append((-1,0))

    # left
    if c-1>=0 and maze[r][c-1][1] == 0:
      directions.append((0,-1))


    for x,y in directions:
      nr,nc = r+x,c+y
      # import pdb; pdb.set_trace()
      if 0 <= nr < h and 0 <= nc < w:
        if dist[nr][nc] != -1: continue
        if (nr,nc) in q: continue
        dist[nr][nc] = dist[r][c] + 1
        if nr == h-1 and nc == w-1:
          break
        else:
          q.append((nr,nc))

  if dist[h-1][w-1] == -1:
    ans.append(0)
    print(0)
  else:
    ans.append(dist[h-1][w-1])
    print(dist[h-1][w-1])


for a in ans:
  print(a)


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

int main(){
  int n,m,i;
  cin >> n >> m;
  if(n>m){
    for(i=0; i<n; i++){
      cout << m;
    }
  }else{
    for(i=0; i<m; i++){
      cout << n;
    }
  }
}

Measured memory_bytes: 256
use std::vec::Vec;

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}

fn main() {
    let n: usize = read();
    let mut s: Vec<char> = read::<String>().chars().collect();

    // s -> true
    // w -> false
    let sw = vec![true, false];
    let mut check = vec![false; n];

    for &first in &sw {
        'label: for &second in &sw {
            check[0] = first;
            check[1] = second;
            // 前の２つにしたがって割り付ける
            for i in 2..n {
                let a = check[i-2]; // ２つ前
                let b = check[i-1]; // １つ前
                allocation(a, b, i, &s, &mut check);
            }


            // checkの割付がsと矛盾しないかを確認
            for i in 0..n {
                let (pre, now, nxt) = if i == 0 {
                   (check[n-1], check[i], check[i+1])
                } else if i == n-1 {
                   (check[i-1], check[i], check[0])
                } else {
                   (check[i-1], check[i], check[i+1])
                };
                
                match (s[i], now) {
                    ('o', true) => {
                        if nxt != pre {
                           continue 'label;
                        }
                    },
                    ('o', false) => {
                        if nxt == pre {
                           continue 'label;
                        }
                    }

                    ('x', true) => {
                        if nxt == pre {
                           continue 'label;
                        }
                    },
                    ('x', false) => {
                        if nxt != pre {
                           continue 'label;
                        }
                    }
                    _  => panic!(),
                }               
            }
            let ans: String = check.into_iter().map(|b| if b { 'S' } else { 'W' }).collect();
            println!("{}", ans);
            return
        }
    }
    println!("-1");
}

// ２つ前と１つ前から現在の要素を確定させる
fn allocation(a: bool, b: bool, index: usize, s: &Vec<char>, check: &mut Vec<bool>) {
    let pre = s[index-1];

    match (pre, b) {
        ('o', true) => check[index] = a,
        ('x', true) => check[index] = !a,
        ('o', false) => check[index] = !a,
        ('x', false) => check[index] = a,
        _ => panic!(),
    }
}


Measured memory_bytes: 4352
program main
    implicit none

!    character,allocatable :: str(:)
     character(:),allocatable :: ca, cb!, cca, ccb
    integer :: nb , ia, ib, i, ma, mb, tena, tenb
    character(100) :: cca, ccb
    character(1) :: a,b 
    

    read(*,*) a, b
    
    read(a,*) ia     ! 内部read文で文字列を整数に変換
    read(b,*) ib     ! 内部read文で文字列を整数に変換


    tena=0
    tenb=0
    
    do i=1,ib
       tena=tena+10**(i-1)
       ma=tena*ia
    enddo
    do i=1,ia
       tenb=tenb+10**(i-1)
       mb=tenb*ib
    enddo

!    print *, ma, mb
    
    write(cca,*) ma    ! 内部write文で整数を文字列に変換
    ca =trim(adjustl(cca)) 
    write(ccb,*) mb    ! 内部write文で整数を文字列に変換
    cb =trim(adjustl(ccb)) 
    
    if(LGE(ca,cb).eqv. .true. ) then
       print *,cb
    else
       print *, ca
    end if


  end program main


Measured memory_bytes: 768
import sys

INF = 10**9+7

stdin = sys.stdin
def na(): return map(int, stdin.readline().split())
def nal(): return list(map(int, stdin.readline().split()))
def ns(): return stdin.readline().strip()
def nsl(): return list(stdin.readline().strip())
def ni(): return int(stdin.readline())


n, c, k = nal()

t = []
for i in range(n):
    t.append(ni())
t.sort()

ans = 0
cnt = 0
tmp = t[0] + k
for i in range(1, n):
    cnt += 1
    if(tmp < t[i] or cnt == c):
        ans += 1
        cnt = 0
        tmp = t[i] + k

print(ans + 1)




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

int main(){
	int a,b;cin>>a>>b;
	int m = max(a,b);
	if( (m*2) <= 16){
		cout << "Yay!" << endl;
	}else{
		cout << ":(" << endl;
	}


	return 0;
}


Measured memory_bytes: 256
#![allow(unused_imports)]
#![allow(clippy::many_single_char_names)]
#![allow(clippy::suspicious_arithmetic_impl)]

// using Rust(1.42.0)
// My Library Repo is at "https://github.com/Loptall/prcn_lib"
// check available crates on AtCoder at "https://atcoder.jp/contests/language-test-202001"

/*
    AtCoder Language Update 2020204 お疲れ様でした! 有難いです(p.s. 過去問対応もありがとうございます)
*/

// from std...
use std::cmp::{max, min, Ordering};
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet, VecDeque};
use std::mem::swap;
use std::ops::*;
use std::usize::{MAX, MIN};
use std::{i128, i16, i32, i64, i8, isize, u128, u16, u32, u64, u8, usize};

// Dep crates are...
use itertools::*;
use itertools_num::*;
use lazy_static::lazy_static;
use maplit::{btreemap, btreeset, hashmap, hashset};
use num_bigint::{BigInt, BigUint};
use num_integer::{binomial, gcd, lcm, Integer};
use permutohedron::Heap;
use petgraph::unionfind::UnionFind;
use proconio::{fastout, input, is_stdin_empty, marker::*};
use rand::random;

// code...
// #[fastout]
fn main() {
    input! {
        a: usize, b: usize, c: usize
    }

    let ans = (a + b) * c / 2;
    println!("{}", ans);
}


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

int main() {
  int k,n;
  cin>>k>>n;
  vector<int>a(n);
  for(int i=0;i<n;i++) cin>>a[i];
  sort(a.begin(),a.end());
  int re=k-a[n-1]+a[0];
  for(int i=0;i<n-1;i++) re=max(a[i+1]-a[i],re);
  cout<<k-re<<endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < (int)(b); i++)
#define all(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const int INF = 1e9;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    int D; //365
    cin >> D;
    int c[26];
    rep(i, 0, 26) {
        cin >> c[i];
    }
    int s[D][26];
    int t[D] = {};
    rep(i, 0, D) {
        int mx = -1;
        rep(j, 0, 26) {
            cin >> s[i][j];
            /*if (mx < s[i][j]) {
                mx = s[i][j];
                t[i] = j;
            }*/
        }
    }


    /*rep(i, 0, D) {
        srand(time(NULL));
        t[i] = rand() % 26;
    }*/

    /*ll mx_score = -1;
    int cnt = 100;
    while (cnt--) {
        srand(time(NULL));
        int d = rand() % 365;
        int q = rand() % 26;
        int old = t[d];
        t[d] = q;

        ll score[D] = {};
        vector<int> last_day(26, -1);
        rep(i, 0, D) {
            if (i != 0) score[i] = score[i - 1];
            score[i] += s[i][t[i]];
            last_day[t[i]] = i;
            int decrease = 0;
            rep(j, 0, 26) {
                decrease += c[j] * (i - last_day[j]);
            }
            score[i] -= decrease;
        }
        if (mx_score > score[D - 1]) {
            t[d] = old;
        } else {
            mx_score = score[D - 1];
        }
    }*/

    rep(i, 0, D) {
        cout << i % 26 + 1 << endl;
    }

    return 0;
}


Measured memory_bytes: 3604
import sys
import numpy as np
from numba import njit

def main(N, S):
    dp = np.zeros((N + 1, N + 1), dtype=np.int64)
    ans = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            dp[i,j] = min(j - i, dp[i - 1,j - 1] + 1) if S[i] == S[j] else 0
        ans = max(ans, np.max(dp[i]))
    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'i8(i8,i8[:])')(main)
    # b1: bool, i4: int32, i8: int64, double: f8, [:], [:, :]
    cc.compile()
else:
    from my_module import main
    N = int(input())
    S = np.array([ord(_) for _ in input()])
    print(main(N, S))


Measured memory_bytes: 286868
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

int main() {
    ll n, *a, *b, *c;   cin >> n;
    a = new ll[n];
    b = new ll[n];
    c = new ll[n];

    for (ll i = 0; i < n; i++)
        cin >> a[i];
    for (ll i = 0; i < n; i++)
        cin >> b[i];
    for (ll i = 0; i < n; i++)
        cin >> c[i];

    sort(a, a+n);
    sort(b, b+n);
    sort(c, c+n);

    ll ans = 0;
    for (int j = 0; j < n; j++) {
        auto x = lower_bound(a, a+n, b[j]);
        auto z = upper_bound(c, c+n, b[j]);

        ll i = distance(a, x);
        ll k = distance(c, z);

        ans += i * (n-k);
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2688
//“Failure is unimportant. It takes courage to make a fool of yourself.”
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
typedef long long int ll;
#define int long long int
#define P 1000000007
#define sz(a) (ll)a.size()
#define lt(a) (ll)a.length()
#define pll pair<ll,ll>
#define f(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define bac(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--)
#define mll map<ll,ll>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(),a.end()
#define F first
#define S second
#define teevra_gati ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define N 1000
#define PI 3.14159265359
#define inf LLONG_MAX
using namespace __gnu_pbds;
using namespace std;


signed main() {
    teevra_gati

    
    ll n,W;
    cin>>n>>W;
    vl w(n+1),v(n+1);
    f(i,1,n+1) cin>>w[i]>>v[i];
    vvl dp(n+1, vl(W+1,0));
    f(i,1,n+1){
        f(j,1,W+1){
            ll p = 0;
            if(j>=w[i]) p = v[i] + dp[i-1][j-w[i]];
            dp[i][j] = max(p,dp[i-1][j]);
        }
    }
    cout<<dp[n][W];
    return 0;
}


Measured memory_bytes: 80256
n=int(input())
t=[2,4,8,16,32,64]
c=0
if n==0:print("0")
elif n==1:print("1")
elif n>=64:print("64")
else:
    for i in t:
        if n < i:
            print(t[c-1])
            break
        c=c+1


Measured memory_bytes: 2940
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int bound = 6600;
const int maxn = 82;
bool dp[maxn][maxn][bound];
int a[maxn][maxn];
int main()
{
  int n,m;
  cin >> n >> m;
  for(int i = 0; i < n; i++)
  {
    for(int j = 0; j < m; j++)
      cin >> a[i][j];
  }
  for(int i = 0; i < n; i++)
  {
    for(int j = 0; j < m; j++)
    {
      int x;
      cin >> x;
      a[i][j] = abs(a[i][j] - x);
    }
  }
  dp[0][0][a[0][0]] = 1;
  for(int i = 0; i < n; i++)
  {
    for(int j = 0; j < m; j++)
    {
      if(i == 0 && j == 0)continue;
      bool t[bound];
      memset(t,0,sizeof(t));
      if(i)
      {
        for(int k = 0; k < bound; k++)
        {
          if(k + a[i][j] < bound) t[k] |= dp[i-1][j][k+a[i][j]];
          t[k] |= dp[i-1][j][abs(k-a[i][j])];
        }
      }
      if(j)
      {
        for(int k = 0; k < bound; k++)
        {
          if(k + a[i][j] < bound) t[k] |= dp[i][j-1][k+a[i][j]];
          t[k] |= dp[i][j-1][abs(k-a[i][j])];
        }
      }
      for(int k = 0; k < bound; k++)
        dp[i][j][k] = t[k];
    }
  }
  for(int i = 0; i < bound; i++)
  {
    if(dp[n-1][m-1][i])
    {
      cout << i << endl;
      exit(0);
    }
  }
}


Measured memory_bytes: 43264
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
4 5
0 1 2
0 2 1
1 2 1
1 3 1
2 3 2

output:
3
"""

import sys
from collections import deque


def bfs(source, target, parent):
    visited = [False] * v_num
    queue = deque()
    queue.appendleft(source)
    visited[source] = True

    while queue:
        current = queue.popleft()
        for adj, cp in adj_table[current].items():
            if cp and not visited[adj]:
                queue.append(adj)
                visited[adj] = True
                parent[adj] = current

    return True if visited[target] else False


def graph_FordFulkerson(source, sink):
    parent = [-1] * v_num
    max_flow = 0

    while bfs(source, sink, parent):
        path_flow = float('inf')
        
        # 1st backward traversal
        bk_1 = sink
        while bk_1 != source:
            parent_bk_1 = parent[bk_1]
            assert parent_bk_1 != -1
            path_flow = min(path_flow, adj_table[parent_bk_1][bk_1])
            bk_1 = parent[bk_1]

        max_flow += path_flow

        # 2nd backward traversal
        bk_2 = sink
        while bk_2 != source:
            parent_bk_2 = parent[bk_2]
            assert parent_bk_2 != -1
            adj_table[bk_2].setdefault(parent_bk_2, 0)
            adj_table[parent_bk_2][bk_2] -= path_flow
            adj_table[bk_2][parent_bk_2] += path_flow
            bk_2 = parent[bk_2]

    return max_flow


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    v_num, e_num = map(int, _input[0].split())
    edges = map(lambda x: x.split(), _input[1:])

    adj_table = tuple(dict() for _ in range(v_num))
    for edge in edges:
        s, t, c = map(int, edge)
        adj_table[s][t] = c

    print(graph_FordFulkerson(source=0, sink=v_num - 1))

Measured memory_bytes: 8180
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = (1953125 << 9);
const ll maxn = 1 * 1e5 + 5;

int a[3], cnt = 0;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout);

	for (int i = 0; i < 3; ++i)
	{
		cin >> a[i];
	}

	sort(a, a + 3);
	while (a[0] != a[2])
	{
		sort(a, a + 3);
		cnt++;
		if(a[1] < a[2])a[0]++,a[1]++;
		else a[0]+=2;
	}
	cout << cnt << endl;

}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#define rep(i,n) for(int i=0;i<(n);i++)
#define SORT(x) (sort(x.begin(),x.end()))
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define psortfirst(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.first<b.first;});
#define All(x) (x).begin(),(x).end()
using namespace std;
using pii  = pair<int,int>;
long long gcd(long long a, long long b){return (b == 0 ? a : gcd(b, a%b));}
long long lcm(long long a, long long b){return a*b/gcd(a,b);}
typedef long long ll;
#define MOD 1000000007
#define EPS 10e-8

int main() {
    ll A[10000000],mi;cin >>A[1];
    mi=A[1];
    for(int i=1;;i++){
        A[i+1]=(A[i]%2==0 ? A[i]/2 : A[i]*3+1 );
        for(int j=1;j<=i;j++){
            if(A[i+1]==A[j]){
                cout << i+1 << endl;
                return 0;
            }
        }
    }
}

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

int lcs(string str1, string str2)
{
	int len[1001][1001] = { 0 };

	int len1 = str1.length();
	int len2 = str2.length();
	str1 = ' ' + str1;
	str2 = ' ' + str2;

	for (int i = 0; i <= len1; i++)
		for (int j = 0; j <= len2; j++) len[i][j] = 0;

	for (int i = 1; i <= len1; i++)
	{
		for (int j = 1; j <= len2; j++)
		{
			if (str1[i] == str2[j]) len[i][j] = len[i - 1][j - 1] + 1;
			else len[i][j] = max(len[i - 1][j], len[i][j - 1]);
		}
	}
	return len[len1][len2];
}

int main()
{
	int n;
	string str1, str2;

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> str1 >> str2;
		cout << lcs(str1, str2) << endl;
	}

	return 0;
}

Measured memory_bytes: 7092
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ALL(a)  (a).begin(),(a).end()
#define PI 3.14159265358979
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll mod = 1e9+7LL;

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const long long INF = 1e10;
long long dp[100010];

int main() {
    int N, K; cin >> N >> K;
    vector<int> h(N);
    rep(i, N) cin >> h.at(i);
    
    rep(i, 100010) dp[i] = INF;
    dp[0] = 0;

    rep(i, N){
        rep(j, K){
            if(i>j) chmin(dp[i], dp[i-j-1] + abs(h[i] - h[i-j-1]));
        }
    }

    cout << dp[N-1] << endl;
}

Measured memory_bytes: 4388
N, x = map(int, input().split())
a = [int(a) for a in input().split()]

if sum(a) == x:
    print(N)
    exit()

sort_a = sorted(a)
count = 0
for i in range(1,N+1):
    if sum(sort_a[:i]) <= x:
        if i < N:
            count += 1
        else:
            pass
    else:
        break

print(count)

Measured memory_bytes: 9120
#include <bits/stdc++.h>
using namespace std;
int main() {
  string s,t;
  cin >> s;
  cin >> t;
  sort(s.begin(),s.end());
  sort(t.begin(),t.end());
  reverse(t.begin(),t.end());
  if(s<t) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
h, w = map(int, input().split())
field = []

for i in range(h):
    field.append(input())

ans = True

for i in range(h):
    if not ans:
        break
    for j in range(w):
        if field[i][j] == '#':
            if i != 0 and field[i - 1][j] == '#':
                continue
            if i != h - 1 and field[i + 1][j] == '#':
                continue
            if j != 0 and field[i][j - 1] == '#':
                continue
            if j != w - 1 and field[i][j + 1] == '#':
                continue
            ans = False
            break

if ans:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <stack>
#include <fstream>
#include <string>
#include <sstream>
#include <algorithm>
#include <climits>
#include <cmath>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
    int x;
    cin >> x;
    if(400 <= x && x < 600) {
    	cout << "8\n";
    } else if(600 <= x && x < 800) {
    	cout << "7\n";
    } else if(800 <= x && x < 1000) {
    	cout << "6\n";
    } else if(1000 <= x && x < 1200) {
    	cout << "5\n";
    } else if(1200 <= x && x < 1400) {
    	cout << "4\n";
    } else if(1400 <= x && x < 1600) {
    	cout << "3\n";
    } else if(1600 <= x && x < 1800) {
    	cout << "2\n";
    } else if(1800 <= x && x < 2000) {
    	cout << "1\n";
    }
	return 0;
}


Measured memory_bytes: 3132
#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=ll(a);i<ll(b);i++)
#define irep(i,a,b) for(ll i=ll(a);i>=ll(b);i--)
#define pb push_back
#define mp make_pair
#define F .first
#define S .second 
using ll=long long;
using ld=long double;
using namespace std;
const ll mod=1e9+7;
ll x[1100][1100];
main(){
    ll h,w,a,b,ans=0;
    cin>>h>>w>>a>>b;
    rep(i,0,h){
       rep(j,0,w){
         x[i][j]=0;
       }
    }
    rep(i,0,b){
       rep(j,0,a){
           x[i][j]=1;
       }
    }
    rep(i,b,h){
       rep(j,a,w){
           x[i][j]=1;
       }
    }
    rep(i,0,h){
       rep(j,0,w){
           cout<<x[i][j];
       }
       cout<<endl;
    }
}



Measured memory_bytes: 9856
#include <stdio.h>
     
using namespace std;
     
int main(){
    int a,b;
    double a_d,b_d;
    scanf("%d %d",&a,&b);
    a_d = static_cast<double>(a);
    b_d = static_cast<double>(b);
    printf("%d %d %.5f\n",a/b,a%b,a_d/b_d);
}


Measured memory_bytes: 2720
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

A, B, C = MAP()

for i in range(2000):
	if (A*i)%B == C:
		print("YES")
		break
else:
	print("NO")


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

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <functional>
#include <math.h>
#include <map>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for(int i=(b-1);i>=(a);--i)
#define REP(i,n)   FOR(i,0,n)
#define RREP(i,n)   RFOR(i,0,n)

const double INF = 1e+09;
const int MOD = 1e9+7;

using namespace std;

template <typename _Ty>
ostream& operator << (ostream& ostr, const vector<_Ty>& v) {if (v.empty()) {ostr << "{ }"; return ostr;}
    ostr << "{" << v.front(); for (auto itr = ++v.begin(); itr != v.end(); itr++) {ostr << ", " << *itr;}
    ostr << "}";
    return ostr;}

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


int main(void){
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<int> a(n-1);
  REP(i, n-1) cin >> a[i];
  vector<int> ans(n);
  vector<int> tmp;
  sort(a.begin(), a.end());
  int conf = 1;
  int val = 0;
  REP(i, n-1){
    if (conf == a[i]){
      val++;
    }
    else{
      int index = conf - 1;
      ans[index] = val;
      val = 1;
      conf = a[i];
    }
    if (i == n-2){
      ans[conf-1] = val;
    }
  }
  REP(i, n){
  cout << ans[i] << endl;
  }

  return 0;}


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

using ll = long long;
#define ALL(c) (c).begin(), (c).end()
const int MOD = 1000000007;

int main() {
    int n;
    cin >> n;
    set<int> s;
    int a;
    for (int i = 0; i < n; i++) {
        cin >> a;
        if (s.count(a) == 1) {
            s.erase(a);
        } else {
            s.insert(a);
        }
    }
    cout << s.size() << endl;
}


Measured memory_bytes: 4864
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
#define mod 200003
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
//(a+b-1)/b
//priority_queue<ll, vector<ll>, greater<ll>> q;
using pl = pair<ll,ll>;
using vvb=vector<vector<bool>>;
using vb= vector<bool>;
ll f(ll a,ll b,ll p){
	if(b==0) return 1;
	if(b%2==0){
		ll t=f(a,b/2,p);
		return t*t%p;
	}
	return a*(f(a,b-1,p))%p;
} 

//__builtin_popcount()
signed main(){
	ll n; cin>>n;
	map<ll,ll> mp;
	mp[1]++;
	mp[2]++;
	mp[3]++;
	rep(i,4,n+1){
		ll k=i;
		for(ll j=2; j*j<=i; j++){
			if(k%j==0){
				while(k%j==0){
					mp[j]++;
					k/=j;
				}
			}
		}
		mp[k]++;
	}
	ll ans=1;
	rep(i,2,n+1){
		ans*=((mp[i]+1)%MOD);
		ans%=MOD;
	}
	cout<<ans<<endl;

	return 0;
}

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

int main()
{
  int64_t N, l = 0, r = 0;
  string S;
  cin >> N >> S;
  for (int i = 0; i < N; i++)
  {
    if (S.at(i) == '(')
      l++;
    else if (l > 0)
      l--;
    else
      r++;
  }
  for (int i = 0; i < r; i++)
    cout << '(';
  cout << S;
  for (int i = 0; i < l; i++)
    cout << ')';
  cout << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;  
#define rep(i, a, b) for(ll i = a; i < b; i++)
#define Rep(i, a, b) for(ll i = a; i <= b; i++)
#define repr(i, a, b) for(ll i = b-1; i >= a; i--)
// #define _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define Vp vector<pair<ll, ll>>
using ll = long long;
#define ALL(v) (v).begin(),(v).end()
#define endl "\n"
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define co(x) cout << x << endl
#define pb push_back
#define sz(v) ((ll)(v).size())
const double pi = acos(-1.0);
const ll MOD = 1000000007LL;
const ll INF = 1LL << 60;
#define pp pair<ll, pair<ll, ll>> 
// #define fi first
// #define se second
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
const int dy[] = {1, 0, -1, 0};
const int dx[] = {0, 1, 0, -1};

/*--------------------------------------------------------------------------------

--------------------------------------------------------------------------------*/

int main() {
    Vl a(2), b(2);
    rep(i, 0, 2) cin >> a[i];
    rep(i, 0, 2) cin >> b[i];
    ll ans = -INF;
    rep(i, 0, 2){
        rep(j, 0, 2){
            chmax(ans, a[i]*b[j]);
        }
    }
    co(ans);

    return 0;
}

Measured memory_bytes: 3624
import java.util.Arrays;
import java.util.Scanner;
class Main{
    public static void main(String args[]){
        Scanner scan = new Scanner(System.in);
        int num = scan.nextInt();
        String[] goods = new String[num];
        int count = 1;
        for(int i = 0; i < num ; i++){
            goods[i] = scan.next();
        }
        Arrays.sort(goods);
        for(int i = 0; i < num-1 ; i++){
            if(goods[i] .equals (goods[i + 1])){
            }else{
                count = count + 1;
            }          
        }
        System.out.println(count);
    }
}

Measured memory_bytes: 70144
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;
typedef long long ll;
#define N 5050
template<typename T>void chkmax(T &x,T y) {x=x>y?x:y;}
int n,m,S[205][N],tp[205],b[N][205];
ll d[N],sum[N],ans;
int main() {
	scanf("%d%d",&n,&m);
	int i,j;
	for(i=2;i<=n;i++) scanf("%lld",&d[i]),d[i]+=d[i-1];
	for(i=1;i<=n;i++) {
		for(j=1;j<=m;j++) {
			scanf("%d",&b[i][j]);
			int t;
			while(tp[j]&&b[i][j]>=(t=b[S[j][tp[j]]][j])) {
				sum[S[j][tp[j]]]-=t;
				sum[S[j][tp[j]-1]]+=t;
				tp[j]--;
			}
			sum[i]+=b[i][j];
			sum[S[j][tp[j]]]-=b[i][j];
			S[j][++tp[j]]=i;
		}
		ll now=0;
		for(j=i;j;j--) {
			now+=sum[j];chkmax(ans,now-d[i]+d[j]);
		}
	}printf("%lld\n",ans);
}


Measured memory_bytes: 6656
#include <iostream>
 #include <string>
 #include <vector>
 #include <algorithm>
 
 using namespace std;
 
 int main(void){
     int a,b;
     cin >> a >> b;
     int c[3]={1,2,3};
     for(int i=0;i<3;i++){
         if(c[i]==a){
             c[i]=0;
         }
         if(c[i]==b){
             c[i]=0;
         }
     }
     for(int i=0;i<3;i++){
         if(c[i]!=0){
             cout << c[i] << endl;
         }
     }
     return 0;
 }

Measured memory_bytes: 256
# A - Double Helix
# A：アデニン T：チミン G：グアニン C：シトシン
# 対になる組み合わせ  A-T  G-C

# 標準入力
base = input()
# print(base)

# 条件分岐し、結果を answer に代入
if base == 'A':
    # print('T')
    answer = 'T'
elif base == 'T':
    # print('A')
    answer = 'A'
elif base == 'G':
    # print('C')
    answer = 'C'
elif base == 'C':
    # print('G')
    answer = 'G'

# 結果の出力
print(answer)


Measured memory_bytes: 8960
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  if(n%1000==0)
    cout<<"0";
  else
  {
    int x=n%1000;
    x=1000-x;
    cout<<x;
  }
  return 0;
}

Measured memory_bytes: 3620
#include<stdio.h>

main(){
  int i,g,f,F[45];
  F[0]=1;
  F[1]=1;
  for(i=2;i<45;i++){
 F[i] = F[i-2] + F[i-1];
}
  scanf("%d",&g);
  printf("%d\n",F[g]);
  return 0;
}

Measured memory_bytes: 596
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
using namespace std;
#define ll long long
#define rep(i, s, n) for(int i = s; i < n; i++)

int main() {
    int n;
    string s;
    cin >> n >> s;
    int right = 0, left = 0;
    for(int i = 0; i < s.size(); i++) {
        if(s[i] == '(') {
            right++;
        }
        else {
            if(right == 0) left++;
            else right--;
        }
    }
    rep(i, 0, left) {
        cout << '(';
    }
    cout << s;
    rep(i, 0, right) {
        cout << ')';
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
n=int(input())
dp=[0]*n
for i in range(n):
	dp[i]=[0]*3
dp[0][0],dp[0][1],dp[0][2]=map(int,input().split())
for i in range(1,n):
	a,b,c=map(int,input().split())
	dp[i][0]=a+max(dp[i-1][2],dp[i-1][1])
	dp[i][1]=b+max(dp[i-1][0],dp[i-1][2])
	dp[i][2]=c+max(dp[i-1][0],dp[i-1][1])
print(max(dp[n-1]))

Measured memory_bytes: 62676
#include<iostream>
#include<string>
#include<sstream>
#include<stack>
#include<cstdio>
#include<cstdlib>
using namespace std;
int main(void){
  stack<double> s;
  string a,d;
  double x,y;
  while(getline(cin,d)){
    for(;!s.empty();) s.pop();
    stringstream ss(d);
    while(ss >> a){
      if(a=="+" || a=="-" || a=="*" || a=="/"){
	y=s.top(),s.pop();
	x=s.top(),s.pop();
	if(a=="+") s.push(x+y);
	else if(a=="-") s.push(x-y);
	else if(a=="*") s.push(x*y);
	else if(a=="/") s.push(x/y);
      }
      else s.push(atof(a.c_str()));
    }
    printf("%.6f\n",s.top());
  }
}


Measured memory_bytes: 1276
s = input()
from collections import Counter
c = Counter(s)
flag = True
if c["S"]>0 and c["N"]==0:
  flag = False
if c["N"]>0 and c["S"]==0:
  flag = False
if c["W"]>0 and c["E"]==0:
  flag = False
if c["E"]>0 and c["W"]==0:
  flag = False
if flag:
  print("Yes")
else:
  print("No")

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

const int MAXN = 100005;
vector<int> edge[MAXN];
bool vis[MAXN];
int n,m,ans[MAXN],dis[MAXN];
int cnt[MAXN];
int main () {
    cin >> n >> m;
    m+=n-1;
    while (m--) {
        int f,t;
        cin >> f >> t;
        edge[f].emplace_back(t);
        cnt[t]++;
    }
    queue<int> pq;
    memset(dis,-1,sizeof dis);
    for (int i=1;i<=n;i++) {
        if(cnt[i] == 0) {
            dis[i] = 0;
            pq.emplace(i);
        }
    }

    while (pq.size()) {
        for (auto v : edge[pq.front()]) {
            dis[v] = max(dis[v],dis[pq.front()]+1);
            if (--cnt[v] == 0) {
                pq.emplace(v);
            }
        }
        pq.pop();
    }

    

    for (int i=1;i<=n;i++) {
        for (auto v : edge[i]) {
            if (dis[v] == dis[i] + 1) {
                ans[v] = i;
            }
        }
    }

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

}

Measured memory_bytes: 7424
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')w=0,ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
#define mk make_pair
int n,m,q,dis[8][8],inf;char s[100005],t[100005];
vector<int>vec[4];queue<pair<int,int> >Q;
void add(int i,int x,vector<int>&v){
	int sz=vec[i].size(),p=lower_bound(vec[i].begin(),vec[i].end(),x)-vec[i].begin();
	if(p)v.push_back(vec[i][p-1]);if(p<sz)v.push_back(vec[i][p]);
}
void upt(int x,int y,int z){
	if(dis[x][y]>z)dis[x][y]=z,Q.push(mk(x,y));
}
int main(){
	n=gi();m=gi();q=gi();scanf("%s%s",s+1,t+1);
	for(int i=1;i<=n;++i)vec[s[i]=='W'?0:1].push_back(i);
	for(int i=1;i<=m;++i)vec[t[i]=='N'?2:3].push_back(i);
	while(q--){
		int a=gi(),b=gi(),c=gi(),d=gi();vector<int>X,Y;
		for(int i=0;i<2;++i)add(i,a,X),add(i,c,X);
		for(int i=2;i<4;++i)add(i,b,Y),add(i,d,Y);
		sort(X.begin(),X.end());X.erase(unique(X.begin(),X.end()),X.end());
		sort(Y.begin(),Y.end());Y.erase(unique(Y.begin(),Y.end()),Y.end());
//		puts("x :");for(int x:X)printf("%d ",x);puts("");
//		puts("y :");for(int y:Y)printf("%d ",y);puts("");
		int lx=X.size(),ly=Y.size();
		int sx=lower_bound(X.begin(),X.end(),a)-X.begin();
		int sy=lower_bound(Y.begin(),Y.end(),b)-Y.begin();
		int tx=lower_bound(X.begin(),X.end(),c)-X.begin();
		int ty=lower_bound(Y.begin(),Y.end(),d)-Y.begin();
		memset(dis,63,sizeof(dis));inf=dis[0][0];dis[sx][sy]=0;Q.push(mk(sx,sy));
		while(!Q.empty()){
			int x=Q.front().first,y=Q.front().second;Q.pop();
//			printf("x=%d y=%d\n",x,y);
			if(s[X[x]]=='W')for(int z=y-1;z>=0;--z)upt(x,z,dis[x][y]+Y[y]-Y[z]);
			else for(int z=y+1;z<ly;++z)upt(x,z,dis[x][y]+Y[z]-Y[y]);
			if(t[Y[y]]=='N')for(int z=x-1;z>=0;--z)upt(z,y,dis[x][y]+X[x]-X[z]);
			else for(int z=x+1;z<lx;++z)upt(z,y,dis[x][y]+X[z]-X[x]);
		}
//		for(int i=0;i<lx;++i,puts(""))
//			for(int j=0;j<ly;++j)
//				printf("%d ",dis[i][j]==inf?-1:dis[i][j]);
		printf("%d\n",dis[tx][ty]==inf?-1:dis[tx][ty]);
	}
	return 0;
}


Measured memory_bytes: 2768
use std::io;

fn main() {
    let mut s = String::new();
    io::stdin().read_line(&mut s).ok();
    s = s.trim_right().to_owned();
    let mut s_vec: Vec<char> = s.chars().collect();
    s_vec.sort();
    if s_vec[0] == s_vec[1] && s_vec[1] != s_vec[2] && s_vec[2] == s_vec[3] {
        println!("Yes");
    } 
    else {
        println!("No");
    }
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define P pair
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define V vector
#define RE return
#define ALL(a) a.begin(),a.end()
#define MP make_pair
#define PB push_back
#define PF push_front
#define FILL(a,b) memset(a,b,sizeof(a))
using namespace std;
int a[100005],n,sum;
int main(){
	ios::sync_with_stdio(0);
    cin.tie(0);
    int h;cin>>h;
	cin>>n;
	FOR(i,1,n)cin>>a[i],sum+=a[i];
	if(sum>=h)cout<<"Yes";else cout<<"No";
	RE 0;
}




Measured memory_bytes: 640
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

int main()
{
    int k, a, b; cin>>k>>a>>b;
    if(a<=b/k*k) cout<<"OK"<<endl;
    else cout<<"NG"<<endl;
    return 0;
}


Measured memory_bytes: 3624
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<limits>
#include<iomanip>
#include<cmath>
#include<climits>

using namespace std;

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

const int mod=1e9+7;

int main(){
    ll n;
    cin >> n;
    string s;
    cin >> s;
    ll numC[26];
    for(int i=0;i<26;i++){
        numC[i]=0;
    }
    for(int i=0;i<s.size();i++){
        numC[s[i]-'a']++;
    }
    ll ans=1;
    for(int i=0;i<26;i++){
        ans=ans*(numC[i]+1)%mod;
    }
    cout << ans-1 << endl;
}


Measured memory_bytes: 512
#include <stdio.h>

int main(void)
{
	int a;
	int i;
	int flag;
	char moji[8] = {0, 1, 2, 3, 5, 7, 8, 9};
	while (1){
		scanf("%d", &a);
		
		if (a == 0){
			break;
		}
		flag = 0;
		for (i = 30; i >= 0; i -= 3){
			if (flag != 0 || moji[(a >> i) & 7] != 0){
				printf("%d", moji[(a >> i) & 7]);
				flag = 1;
			}
		}
		printf("\n");
	}
	
	return (0);
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
int main(){
  vector<bool> prime(100001, true);
  prime[0] = false;
  prime[1] = false;
  for (int i = 2; i <= 100000; i++){
    if (prime[i]){
      for (int j = i * 2; j <= 100000; j += i){
        prime[j] = false;
      }
    }
  }
  vector<int> p(100001, 0);
  for (int i = 1; i <= 100000; i++){
    for (int j = 1; j * j <= i; j++){
      if (i % j == 0){
        p[i] = j;
      }
    }
  }
  while (1){
    int m, a, b;
    cin >> m >> a >> b;
    if (m == 0 && a == 0 && b == 0){
      break;
    }
    int ans = 0;
    while (1){
      if (prime[p[m]] && prime[m / p[m]]){
        if (a * (m / p[m]) <= b * p[m]){
          cout << p[m] << ' ' << m / p[m] << endl;
          break;
        }
      }
      m--;
    }
  }
}


Measured memory_bytes: 3352
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+9;
ll arr[maxn];
int main(){
    ios::sync_with_stdio(0);
    ll a,b,c,d,e,f,g,h,n;
    cin>>a>>b;
    e=min(a,b),f=max(a,b);
    if(f<2){
        cout<<"Brown"<<endl;
    }
    else{
        if(f-e>1){
            cout<<"Alice"<<endl;
        }
        else{
            cout<<"Brown"<<endl;
        }
    }
    return 0;
}


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

#define sz(x) int(x.size())
#define pii pair<int, int>
#define All(x) (x).begin(), (x).end()
#define mp make_pair
#define Task "abc"

typedef long long ll;
const int maxn = 1e5 + 10;
const ll mod = 1e9 + 7;
const int inf = 2e9;

int n;
int root[maxn];

struct Edge{
  int u, v, l;
  Edge(int _u = 0, int _v = 0, int _l = 0) : u(_u), v(_v), l(_l) {}
  bool operator < (const Edge &op) const {
    return l < op.l;
  }
};
Edge e[maxn * 2];

pair<pii,int> a[maxn];

int getroot(int u){
  return (u == root[u] ? u : (root[u] = getroot(root[u])) );
}

int main(){
  ios_base::sync_with_stdio(0); cin.tie(NULL);
//  freopen(Task".inp", "r", stdin); freopen(Task".out", "w", stdout);
  cin >> n;
  #define fi first
  #define se second
  for (int i = 1; i <= n; ++i){
    cin >> a[i].fi.fi >> a[i].fi.se;
    a[i].se = i;
  }
  int m = 0;
  sort(a + 1, a + n + 1, [](pair<pii, int> x, pair<pii, int> y){
    return x.fi.fi < y.fi.fi;
  });
  for (int i = 1; i < n; ++i){
    e[++m] = Edge(a[i].se, a[i+1].se, a[i+1].fi.fi - a[i].fi.fi);
  }
  sort(a + 1, a + n + 1, [](pair<pii, int> x, pair<pii, int> y){
    return x.fi.se < y.fi.se;
  });
  for (int i = 1; i < n; ++i){
    e[++m] = Edge(a[i].se, a[i+1].se, a[i+1].fi.se - a[i].fi.se);
  }
  sort(e + 1, e + m + 1);
  int nt = 0;
  ll ans = 0;
  for (int i = 1; i <= n; ++i) root[i] = i;

  for (int i = 1; i <= m; ++i){
    if (nt == n - 1) break;
    int u = e[i].u, v = e[i].v, l = e[i].l;
    int ru = getroot(u), rv = getroot(v);
    if (ru == rv) continue;
    root[rv] = ru;
    ans = ans + l;
  }
  cout << ans;
return 0;
}




Measured memory_bytes: 4224
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#define maxn 2000000
using namespace std;
int n;
char s[maxn];
int main() {
    scanf("%d",&n);
    scanf("%s",s);
    int ans=0,r=0;
    for(int i=0;i<n;i++) {
        if(s[i]=='R') r++;
    }
    for(int i=0;i<r;i++) {
        if(s[i]=='W') ans++;
    }
    printf("%d",ans);
	return 0;
}


Measured memory_bytes: 4012
n=int(input())
a=list(map(int,input().split()))
b=sorted(a,reverse=True)

ans=1
if b[-1]==0:
    print(0) 
else:
    for i in a:
        ans=ans*i
        if ans>10**18:
            print(-1)
            break
    else:
        print(ans)

Measured memory_bytes: 21696
//https://atcoder.jp/contests/abc127/tasks/abc127_d

import java.util.Scanner;
import java.util.HashMap;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collections;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        ArrayList<Integer> A = new ArrayList<>();
        for (int i=0;i<N;i++){
            A.add(sc.nextInt());
        }
        HashMap<Integer,Integer> map = new HashMap<>();
        ArrayList<Integer> keys = new ArrayList<>();
        for (int i=0;i<M;i++){
            int B = sc.nextInt();
            int C = sc.nextInt();
            if (map.containsKey(C)){
                map.put(C,map.get(C)+B);
            } else {
                map.put(C,B);
                keys.add(C);
            }
        }
        Collections.sort(keys,Collections.reverseOrder());
        Collections.sort(A);
        int now = 0;
        for (int key:keys){
            int b = 0;
            for (int i=now;i<N;i++){
                now = i;
                if (A.get(i)<key){
                    A.set(i,key);
                    b++;
                }
                if (b>=map.get(key)){
                    break;
                }
            }
        }
        long ans = 0;
        for (int a:A){
            ans+=a;
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 104364
#include <bits/stdc++.h>
#define ll unsigned long long
using namespace std;
const int N=1e6;
int n,k,a[N],z[2]={1,-1},laz;
char s[N];
int main(){
    cin>>n>>k>>s;
    for (int i=0; i<n; ++i)
	a[i+1]=s[i]-'A';
    int l=1,r=n,cnt=0;
    while(k&&cnt<2*n){
	--k,++cnt;
	if (a[l]==laz)
	    a[l]^=1;
	else
	    ++l,++r,laz^=1,a[r]=laz;
    }
    if (k&1)
	if (a[l]==laz)
	    a[l]^=1;
	else
	    ++l,++r,laz^=1,a[r]=laz;
    for (int j=l; j<=r; ++j) putchar('A'+(a[j]^laz));
    putchar('\n');
    return 0;
}


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

#define int long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define uniqueV(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))
#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))
#define dbg(x) cerr << #x << ": " << x << endl;
#define dbg2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define dbg3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;
#define dbgB(value, size) cerr<<#value<<": "<<bitset<size>(value) << endl;
#define line() cerr << "---------------" << endl;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const double PI = 3.14159265358979323846;

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

template<typename T>
void print1(T begin, T end) {
	while (begin != end) {
		cerr << (*begin) << " ";
		*begin++;
	}
	cerr << endl;
}

template<typename T>
void print2(T Array, int height, int width) {
	for (int i = 0; i < height; i++) {
		for (int j = 0; j < width; j++) {
			cerr << " " << Array[i][j];
		}
		cerr << endl;
	}
}

void print() { std::cerr << endl; }
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
	std::cerr << head << " ";
	print(std::forward<Tail>(tail)...);
}

template<class T>
void Add(T &a, const T &b, const T &mod=1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}

template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

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

using pii = pair<int, int>;
int N, L;

signed main() {
	cin >> N >> L;
	vec<pii> v;
	rep (i, N) {
		int ii = i + 1;
		v.push_back({abs(L+ii-1), L+ii-1});
	}
	sort(all(v));
	// print1(all(v));

	int ans = 0;
	repp (i, 1, N) {
		ans += v[i].second;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
	int n, m;
	int a[100][100], b[100];
	int i, j;
	int sum;
	scanf("%d %d", &n, &m);
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++) {
			scanf("%d", &a[i][j]);
		}
	}
	for (j = 0; j < m; j++) scanf("%d", &b[j]);
	for (i = 0; i < n; i++) {
		sum = 0;
		for (j = 0; j < m; j++) {
			sum += a[i][j] * b[j];
		}
		printf("%d\n", sum);
	}

	return 0;
}


Measured memory_bytes: 2044
fun main(args: Array<String>) {
    val (A, B, C, K) = readLine()!!.split(" ").map { it.toLong() }

//    var amount = K
    
//    val a = if (amount > A) {
//        amount -= A
//        A
//    } else {
//        val tmp = amount
//        amount = 0
//        tmp
//    }
//
//    val b = if (amount > B) {
//        amount -= B
//        B
//    } else {
//        val tmp = amount
//        amount = 0
//        tmp
//    }
//
//    val c = if (amount > C) {
//        amount -= C
//        C
//    } else {
//        amount
//    }
    fun calc(numElemnts: List<Long>, amount: Long, calcResult: List<Long> = listOf(), index: Int = 1): List<Long> {
        val targetNum = numElemnts[index - 1]
        val (newAmount, addElement) = if (amount > targetNum) Pair(amount - targetNum, targetNum) else Pair(0L, amount)
        val newCalcResult = calcResult.plusElement(addElement)
    
        return if (index == numElemnts.size) {
            newCalcResult
        } else calc(numElemnts, newAmount, newCalcResult, index + 1)
    }
    
    val (a, _, c) = calc(listOf(A,B,C), K)

    println(a - c)
}



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

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

	vector<int> c(n),s(n),f(n); for (int i = 1; i < n; i++) cin >> c[i] >> s[i] >> f[i];

	for (int k = 1; k < n; k++) {

		int ans = 0;

		for (int i = k; i < n; i++) {

			if (i == k) {
				ans += s[i];
				ans += c[i];
				continue;
			}
			
			if (ans <= s[i]) {
				ans += s[i] - ans;
			}
			else {
				int tmp = (ans - s[i]) % f[i];
				if (tmp != 0) {
					ans += f[i] - tmp;
				}			
			}
			ans += c[i];
				
		}
		cout << ans << endl;
	}
		
	cout << 0 << endl;	
	return 0;
}

Measured memory_bytes: 256
n,k = map(int,input().split())
A = list(map(int,input().split()))
imos = [0]*(n+1)
for j in range(k):
    if j==0:
        arr = A
    else:
        arr = imos
    imos = [0]*(n+1)
    for i,a in enumerate(arr):
        imos[max(i-a, 0)] += 1
        imos[min(i+a+1, n)] -= 1
    for k in range(1, len(imos)):
        imos[k] = imos[k]+imos[k-1]
    imos = imos[:-1]
    if set(imos)=={n}:
        break
print(*imos)

Measured memory_bytes: 168744
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>

using namespace std;

int main(){
    long long int n,sum = 0;
    map<long long int,long long int>m;
    vector<long long int>v(n);
    cin >> n;

    for(int i = 0;i < n;i++){
        cin >> v[i];
        m[v[i]]++;
    }

    for(auto &i:m)
        sum += i.second*(i.second-1)/2;

    for(int i = 0;i < n;i++){
        cout << sum-m[v[i]]+1 << endl;
    }

    return 0;
}

Measured memory_bytes: 42240
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
from functools import lru_cache
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))
def inpl_str():
    '''
    一行に複数の文字
    '''
    return list(input().split())

n, k = inpl()
max_value = 10 ** 5 + 1
# max_value=140+1
dp = [[INF] * max_value for i in range(n + 1)]
dp[0][0]=0
for i in range(n):
    w, v = inpl()
    for j in range(max_value):
        include = dp[i][j-v] + w if j-v>=0 else INF
        not_include = dp[i][j]
        dp[i + 1][j] = min(include, not_include)
tmp = dp[n][:]
for i in range(max_value-1, -1, -1):
    if tmp[i] <=k:
        print(i)
        break
# for i in dp:
#     print(i)

Measured memory_bytes: 313412