akhauriyash/Code-Regression huggingface dataset:
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#include<algorithm>//next_permutation
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
#define dec(n) cout << fixed << setprecision(n);
#define large "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define small "abcdefghijklmnopqrstuvwxyz"
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;

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

const ll MOD = 998244353;
const ll MAX = 2000001;

ll mod(ll a){
  if(a % MOD < 0) return MOD + (a % MOD);
  return a % MOD;
}

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


int main(){
  ll n; cin >> n; ll ans = 0;
  
  rep(i,n){
    ll l,r; cin >> l >> r;
    ans += r-l+1;
  }
  
  cout << ans << endl;
}

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

const int MAX = 100005;
const int INFTY = 1000000005;
const int WHITE = 0;
const int BLACK = 1;
pair<int, int> X[MAX], Y[MAX];
vector<pair<int, int>> adj[MAX];
int N;

long long prim() {
    long long sum = 0ll;
    int d[MAX], color[MAX];
    priority_queue<pair<int, int>> PQ;

    for (int i = 0; i < N; i++) {
        d[i] = INFTY;
        color[i] = WHITE;
    }

    d[0] = 0;
    PQ.push(make_pair(0, 0));

    while (!PQ.empty()) {
        pair<int, int> f = PQ.top(); PQ.pop();
        int u = f.second;
        if (color[u] == BLACK) continue;
        color[u] = BLACK;
        d[u] = -f.first;
        sum += -f.first;


        for (int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i].second;
            if (color[v] == BLACK) continue;
            PQ.push(make_pair(-adj[u][i].first, v));
        }
    }

    return sum;
}

int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &X[i].first, &Y[i].first);
        X[i].second = Y[i].second = i;
    }
    sort(X, X+N);
    sort(Y, Y+N);
    for (int i = 1; i < N; i++) {
        adj[X[i-1].second].push_back(make_pair(X[i].first-X[i-1].first, X[i].second));
        adj[X[i].second].push_back(make_pair(X[i].first-X[i-1].first, X[i-1].second));
        adj[Y[i-1].second].push_back(make_pair(Y[i].first-Y[i-1].first, Y[i].second));
        adj[Y[i].second].push_back(make_pair(Y[i].first-Y[i-1].first, Y[i-1].second));
    }

    long long ans = prim();
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 11000
A, B = map(int, input().split())

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y) #再帰定義
n = gcd(A,B)

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
  
L = sorted(make_divisors(n))
tmp = []
for i in range(len(L)):
  e = L[i]
  if e == 1:
    tmp.append(e)    
  else:
    f = 0
    for j in range(len(tmp)):      
      if gcd(e,tmp[j]) != 1:
        f = 1
        if tmp[j] == 1:
          f = 0
    if f == 0:
      tmp.append(e)

print(len(tmp))

Measured memory_bytes: 46448
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll aa[100009],b,c,d,n,mn=1e10,k,mod=1e9+7,dp[100009];
char C[1009][1009];
ll a[1009][1009];
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=k;j++)
        {
            cin>>C[i][j];
        }
    }
    a[1][1]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=k;j++)
        {
            if(i==1&&j==1){continue;}
            if(C[i][j]!='#')
            {
                a[i][j]=((a[i-1][j]+a[i][j-1])%(mod));
            }
        }
    }
    cout<<a[n][k];
}


Measured memory_bytes: 10496
#include<stdio.h>
int main(){
    int a[3];
    int i,j,tmp;
    scanf("%d%d%d",&a[0],&a[1],&a[2]);
    for(i=0;i<3;i++){
        for(j=1;i<=j;j--){
            if(a[j]>a[j+1]){
                tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;
            }
        }
    }
    printf("%d %d %d\n",a[0],a[1],a[2]);
    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#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 perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define all(x) (x).begin(),(x).end()
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
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};
using Graph = vector<vector<int>>;
const ll mod=1000000007;
const int MAX_N = 1000;         // n の最大値
 
double nCk(int n, int k) {
double res=1.0;
for(int i=0; i<n; i++){
res*=0.5;}
for(int i=0; i<k; i++){
res*=(double)(n-i);
res/=(double)(k-i);
}
return res;}
 
int main() {
ll n,k;
cin>>n>>k;
if(k==1){
cout << 0 << endl;}
else{
cout << n-k << endl;}}


Measured memory_bytes: 3632
import collections

n=int(input())
arr=list(map(int,input().split()))
cnt=collections.defaultdict(int)
for val in arr:
  cnt[val]+=1
sums=sum(arr)
q=int(input())
for _ in range(q):
  b,c=map(int,input().split())
  diff=(c-b)*(cnt[b])
  sums+=diff
  print(sums)
  cnt[c]+=cnt[b]
  cnt[b]=0

Measured memory_bytes: 89268
from collections import deque

s = list(input())
s = deque(s)
n = len(s)
t = input()

for _ in range(n):
    a = s.pop()
    s.appendleft(a)
    ss = "".join(s)
    if ss == t:
        print("Yes")
        exit()
else:
    print("No")

Measured memory_bytes: 3316
n = int(input())
a = [int(i) for i in input().split()]

maxa = max(a)
l = [0] * (maxa+1)


for i in a:

    c = 1
    while True:
        if i*c >= maxa+1:
            break
        l[i*c - 1] += 1
        c += 1







ans = 0

for i in set(a):
    if l[i-1] == 1:
        ans += 1

print(ans)


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

int main(){
    int a,b;
    cin>>a>>b;
    if(a==b) cout<<"Draw"<<endl;
    else{
        if(a==1) cout<<"Alice"<<endl;
        else if(b==1) cout<<"Bob"<<endl;
        else{
            if(a>b) cout<<"Alice"<<endl;
            else cout<<"Bob"<<endl;
        }
    }
}

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

#define REP(i,n) for(int i = 0;i < n;i++)
#define REPR(i,n) for(int i = n-1;i >= 0;i--)
#define FOR(i,m,n) for(int i = m;i < n;i++)
#define INF 2e9
#define ALL(v) v.begin(),v.end()
#define ll long long
#define GREATER greater<int>()

using namespace std;

string pop_back(string s){
    string t = s.substr(0,s.size()-1);
    return t;
}

int gcd(int max,int min){
    
    if(max<min){
        int tmp=max;
        max=min;
        min=tmp;
    }

    if(max%min==0)return min;
    else return gcd(min,max%min);

}

int main(void){

    int a,b,c;
    cin>>a>>b>>c;
    cout<<min(b/a,c)<<endl;

    return 0;
}




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

int main() {
  int A, B, T;
  cin >> A >> B >> T;
  int output = 0;
  for (int i = 1; i < 100; i++) {
    
    if (T - A >= 0) {
      T -= A;
      output += B;
    } else {break;}
    
  }
  
  cout << output << endl;
  
  return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-


def check(s, t):
  len_s = len(s)
  if len_s < 1 or 10 < len_s:
    return False

  len_t = len(t)
  if not len_t == len_s + 1:
    return False

  if t.find(s) == 0:
    return True

  return False


#
#
s = input()
t = input()

if check(s, t):
  print("Yes")
else:
  print("No")

Measured memory_bytes: 8920
n = int(input())
cnt = 0
st = "No"
for _ in range(n):
    l1,l2 = map(int,input().split())
    if l1 == l2 :
        cnt += 1
    else:
        cnt = 0
    if cnt == 3:
        st = "Yes"
        
print(st)

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

typedef long long ll;
using namespace std;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	std::cout.setf(std::ios_base::fixed,std::ios_base::floatfield);

	int n,t; cin >> n >> t;
	double tan[1005];

	int x,h;
	for (int i = 0;i < n;i++){
		cin >> x >> h;
		tan[i] = (double)h/x;
	}

	sort(tan,tan+n);

	cout << tan[n-1]*t << endl;

	return 0;

}



Measured memory_bytes: 3308
#include<stdio.h>

int main(){
    int a,b,c,d;
    char *s;
    scanf("%d%d%d%d",&a,&b,&c,&d);
    if(abs(a-c)<=d) s="Yes";
    else if(abs(a-b)<=d && abs(b-c)<=d) s="Yes";
    else s="No";
    printf("%s",s);
}

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


int main(){
    int n , mistake = 0;
    cin >> n;
    vector<int> yiyi(n);
    for(int i = 0 ; i < n;i++){
        cin >> yiyi.at(i);
    }
    for(int i = 0 ; i < n;i++){
        if(yiyi.at(i) == (i+1)){
            mistake++;
            i++;
        }
    }
    cout << mistake << endl;
}

Measured memory_bytes: 640
#define _GLIBCXX_DEBUG
#pragma GCC diagnostic ignored "-Wsign-compare"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < int(n); ++i)

double th = M_PI * 60.0 / 180.0;

void koch(int d, pair<double, double> p1, pair<double, double> p2) {
    if (d == 0) {
        return;
    }
    pair<double, double> s, u, t;
    s = {(2.0 * p1.first + p2.first) / 3.0, (2.0 * p1.second + p2.second) / 3.0};
    t = {(p1.first + 2.0 * p2.first) / 3.0, (p1.second + 2.0 * p2.second) / 3.0};
    u.first = (t.first - s.first) * cos(th) - (t.second - s.second) * sin(th) + s.first;
    u.second = (t.first - s.first) * sin(th) + (t.second - s.second) * cos(th) + s.second;
    koch(d - 1, p1, s);
    cout << s.first << " " << s.second << "\n";
    koch(d - 1, s, u);
    cout << u.first << " " << u.second << "\n";
    koch(d - 1, u, t);
    cout << t.first << " " << t.second << "\n";
    koch(d - 1, t, p2);
}

void solve() {
    int n;
    cin >> n;
    cout << 0.0 << " " << 0.0 << "\n";
    koch(n, {0, 0}, {100, 0});
    cout << 100.0 << " " << 0.0 << "\n";
}
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
}


Measured memory_bytes: 3484
#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <bitset>
#include <complex>
#include <unistd.h>
#include <cassert>
#include <cctype>
#include <random>
#define _USE_MATH_DEFINES
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef pair<double, ll> pdlg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef tuple<double, double, double> tddd;
typedef complex<double> xy_t;
#define REP(i, x, y) for(ll i = x; i < y; i++)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
double pi = 3.141592653589793;
ll mod = 1000000007;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;
int iinf = intmax / 8;
ll inf = llmax / 8;
double eps = 1e-11;

ll b[100010];
plglg c[100010];
ll bsum[100010];
ll mark[100010];

ll bit[1000010], n;

ll sum(int i) {
    ll s = 0;
    while (i > 0) {
        s += bit[i];
        i -= i & -i;
    }
    return s;
}

void add(int i, ll x) {
    while (i <= n) {
        bit[i] += x;
        i += i & -i;
    }
}

int main() {
    ll N;
    cin >> N;
    ll a[N];
    REP(i, 0, N) {
        cin >> a[i];
    }
    if (N == 1) {
        cout << a[0] << endl;
        return 0;
    }
    ll hi = 1e9 + 1;
    ll lo = 0;
    while (hi - lo > 1) {
        ll mid = (hi + lo) / 2;
        REP(i, 0, N) {
            if (a[i] >= mid) {
                b[i] = 1;
            } else {
                b[i] = -1;
            }
        }
        bsum[0] = b[0];
        REP(i, 1, N) {
            bsum[i] = bsum[i - 1] + b[i];
        }
        REP(i, 0, N) {
            c[i] = plglg(bsum[i], i);
        }
        sort(c, c + N);
        mark[c[0].second] = 1;
        ll tmp = 1;
        REP(i, 1, N) {
            if (c[i].first != c[i - 1].first) {
                tmp++;
            }
            mark[c[i].second] = tmp;
        }
        n = tmp;
        fill(bit, bit + n + 1, 0);
        ll inv = 0;
        REP(i, 0, N) {
            inv += i - sum(mark[i]);
            add(mark[i], 1);
        }

        ll num = N * (N - 1) / 2 - inv;
        //cout << mid << " " << num << endl;
        ll pl = lower_bound(c, c + N, plglg(0, 0)) - c;
        //cout << inv << " " << pl << endl;
        if (num + (N - pl) >= (N * (N + 1) / 2 + 1) / 2) {
            lo = mid;
        } else {
            hi = mid;
        }
    }
    cout << lo << endl;
}


Measured memory_bytes: 7424
n=input()
if n=="999":
    print(111)
elif n=="991":
    print(119)
elif n=="911":
    print(199)
elif n=="919":
    print(191)
elif n=="111":
    print(999)
elif n=="119":
    print(991)
elif n=="199":
    print(911)
else:
    print(919)

Measured memory_bytes: 3060
package main
import(
  "fmt"
)
func main(){
  var a, b int
  fmt.Scan(&a, &b)
  ans:=1
  i:=0
  l:
    for{
      i+=a
      if i>=b{
        break l
      }
      ans++
      i--
    }
  if b==1{
    fmt.Println("0")
    }else{
    fmt.Println(ans)
  }
}


Measured memory_bytes: 512
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<iomanip>
#include<string>
#include<queue>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>

#define int long long

using namespace std;

const int INF = 1e17 + 7;

vector<vector<int>> grid;
vector<string> gr;

void bfs(int X, int Y) {
    deque <pair<int, int>> q;
    q.push_front({ X, Y });
    while (q.size()) {
        int x = q.begin()->first, y = q.begin()->second;
        q.pop_front();
        for (int i = -1; i <= 1; ++i) {
            if (0 <= x + i && x + i < grid.size() &&
                gr[x + i][y] == '.') {
                if (grid[x + i][y] > grid[x][y]) {
                    q.push_front({ x + i, y });
                    grid[x + i][y] = grid[x][y];
                }
            }
        }
        for (int i = -1; i <= 1; ++i) {
            if (0 <= y + i && y + i < grid[0].size() &&
                gr[x][y + i] == '.') {
                if (grid[x][y + i] > grid[x][y]) {
                    q.push_front({ x, y + i });
                    grid[x][y + i] = grid[x][y];
                }
            }
        }
        for (int i = -2; i <= 2; ++i) {
            for (int j = -2; j <= 2; ++j) {
                if (0 <= x + i && x + i < grid.size() &&
                    0 <= y + j && y + j < grid[0].size() &&
                    gr[x + i][y + j] == '.') {
                    if (grid[x + i][y + j] > grid[x][y] + 1) {
                        q.push_back({ x + i, y + j });
                        grid[x + i][y + j] = grid[x][y] + 1;
                    }
                }
            }
        }
    }
}

void solve() {
    int n, m, x1, y1, x2, y2;
    cin >> n >> m >> x1 >> y1 >> x2 >> y2;
    --x1, --y1, --x2, --y2;
    grid.resize(n, vector<int>(m, INF));
    gr.resize(n);
    for (auto& s : gr) cin >> s;
    grid[x2][y2] = 0;
    bfs(x2, y2);
    if (grid[x1][y1] == INF) cout << -1;
    else cout << grid[x1][y1];
}

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

    int t = 1;
    //cin >> t;
    while (t--) solve();

    return 0;
}

Measured memory_bytes: 12656
H,W = map(int, input().split())
fields =  [list(input()) for i in range(H)]
# print(fields)

from collections import deque
cnts = [[1000] * W for i in range(H)]
q = deque()
q.append((0,0))
cnts[0][0] = 0
str_s = "."
mv = [(1,0),(0,1)]
while len(q) > 0:
    h,w = q.popleft()
    # mark = fields[h][w]
    for dh, dw in mv:
        if h + dh < H and w + dw < W:
            # print("upd",h,w,h+dh,w+dw,H,W)
            if fields[h][w] == fields[h+dh][w+dw]:
                upd = cnts[h][w] 
            else:
                if fields[h][w] == ".":
                    upd = cnts[h][w] + 1
                else:
                    upd = cnts[h][w]
            if cnts[h+dh][w+dw] > upd:
                cnts[h+dh][w+dw] = min(cnts[h+dh][w+dw],upd)
                q.append((h+dh,w+dw))

# print(cnts)

ans = cnts[H-1][W-1]
if fields[0][0] == "#":ans += 1
print(ans)



Measured memory_bytes: 44272
#include<cstdio>

char map[10][10];

int dx[]={-1,0,1,-1,0,1,-1,0,1}, dy[]={1,1,1,0,0,0,-1,-1,-1};
int cnt(int x, int y, int n, int dir, char me) {
    if(!(x>=0 && y>=0 && x<8 && y<8)) return 0;
    if(map[y][x] == '.') return 0;
    if(map[y][x] == me) return n-1;
    return cnt(x+dx[dir], y+dy[dir], n+1, dir, me);
}
int cnt(int x, int y, char me) {
    int res=0;
    for(int i=0; i<9; i++)
        res+=cnt(x+dx[i],y+dy[i],1,i,me);
    return res;
}
bool replace(int x, int y, int n, int dir, char me) {
    if(!(x>=0 && y>=0 && x<8 && y<8)) return false;
    if(map[y][x] == '.') return false;
    if(map[y][x] == me) return true;

    bool res=replace(x+dx[dir], y+dy[dir], n+1, dir, me);
    if(res)
        map[y][x] = me;
    return res;
}
void replace(int x, int y, char me) {
    map[y][x] = me;
    for(int i=0; i<9; i++)
        replace(x+dx[i],y+dy[i],1,i,me);
}
bool finish() {
    for(int i=0; i<8; i++)
        for(int j=0; j<8; j++)
            if(map[j][i] == '.') return false;
    return true;
}
int main(void) {
    for(int j=0; j<8; j++)
        scanf("%s",map[j]);

    char c[]={'o','x'};
    bool flag=false;
    for(int turn=0; ; turn=1-turn) {
        int rx,ry,max=0;
        for(int i=0; i<8; i++)
            for(int j=0; j<8; j++) {
                if(map[i][j] != '.') continue;
                int t = cnt(j,i,c[turn]);
                if(turn)
                    if(max<=t)
                        max=t, rx=j, ry=i;
                    else;
                else
                    if(max<t)
                        max=t, rx=j, ry=i;
            }
        if(max) replace(rx, ry, c[turn]),flag=false;
        else
            if(flag) break;
            else flag=true;
    }

    for(int j=0; j<8; j++)
        printf("%s\n",map[j]);

    return 0;
}

Measured memory_bytes: 948
def check(player):
    if not a[player]:
        return
    opponent = a[player][-1]
    if not a[opponent]:
        return
    if a[opponent][-1] == player:
        tpl = (player, opponent)
        q.add((min(tpl), max(tpl)))


n = int(input())

a = []
for _ in range(n):
    t = list(map(lambda x: int(x) - 1, input().split()))
    t.reverse()
    a.append(t)

q = set()
for i in range(n):
    check(i)

day = 0
while q:
    day += 1
    prev_q = set()
    q, prev_q = prev_q, q
    for player, opponent in prev_q:
        a[player].pop()
        a[opponent].pop()
    for player, opponent in prev_q:
        check(player)
        check(opponent)

if any(a[player] for player in range(n)):
    print(-1)
    exit()

print(day)

Measured memory_bytes: 35060
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<tuple>
#include<sstream>
#include<math.h>
#include<iomanip>
#define rep(i,n) for(int i =0;i<(int)(n);i++)
typedef long long ll;
using namespace std;
typedef long double ld;
ld facctorialMethod(ld k) {
	ld sum = 1;
	for (ld i = 1; i <= k; ++i)
	{
		sum *= i;
	}
	return sum;
}
int main() {
	ld n;
	cin >> n;
	vector<ld>x(n);
	vector<ld>y(n);
	rep(i, n) {
		cin >> x[i] >> y[i];
	}
	ld len = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			len += sqrt((x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j])) * 2 * facctorialMethod(n - 1);
		}
	}
	len /= facctorialMethod(n);
	cout << setprecision(10) << len << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=410;
const ll mod = 1e9+7 ; 
ll a[N],b[N];
ll sum[N][N], l[N][N];
ll dp[N][N];
int main(){
    ll n,m;
    scanf("%lld%lld",&n, &m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%lld",&b[i]);
    }
    for(int i=0; i<N; i++){
        l[i][0]=1;
        for(int j=1; j<N; j++){
            l[i][j]=(l[i][j-1]*i)%mod;
        }
    }
    for(int i=1; i<N; i++){
        for(int j=0; j<N; j++){
            sum[i][j]=(sum[i][j]+sum[i-1][j]+l[i][j])%mod;
        }
    }
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            for(int k=0;k<=j;k++){
                dp[i][j]=((dp[i][j]%mod+(1ll*dp[i-1][j-k]*(sum[b[i]][k]-sum[a[i]-1][k]))%mod+mod)%mod+mod)%mod;
            }
        }
    }
    printf("%lld\n",(dp[n][m]+mod)%mod);
    //system("pause");
    return 0;
}

Measured memory_bytes: 4224
def main():
    from collections import Counter
    n, m, *abc = map(int, open(0).read().split())
    a = Counter(abc[:n])
    bc = abc[n:]
    for i, j in zip(*[iter(bc)] * 2):
        a[j] += i

    cnt = n
    ans = 0
    keys = list(a.keys())
    keys.sort(reverse=True)

    for k in keys:
        m = a[k]
        if m <= cnt:
            ans += k * m
            cnt -= m
        else:
            ans += k * cnt
            break

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 41408
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    s = S()
    s.append("o")
    a = s.count("o")-1
    print(700+a*100)
    return

#B
def B():
    n, x = LI()
    m = IR(n)
    m.sort()
    msum = sum(m)
    print(n + (x - msum) // m[0])
    return

#C
def C():
    a, b, c, x, y = LI()
    if c * 2 > a + b:
        print(x * a + y * b)
        return
    if x > y:
        if c * 2 > a:
            print(c * 2 * y + (x - y) * a)
            return
        print(c * 2 * x)
        return
    if c * 2 > b:
        print(c * 2 * x + (y - x) * b)
        return
    print(c * 2 * y)

    return

#D
def D():
    return

#Solve
if __name__ == '__main__':
    C()


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

using namespace std;

int main(){
    
    int x, a, b;
    scanf("%d %d %d", &x, &a, &b);
    
    if(abs(x-a)<abs(x-b)) printf("A\n");
    else printf("B\n");
    
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int mp[15][15];
int main(){
  long long l,r;cin>>l>>r;
  // 2019
  
  if(r-l>=2019){
    cout<<0<<endl;
  }else{
    long long result = 2019;
    for(long long i=l;i<=r;++i){
      for(long long j=l;j<i;++j){
        result = min(result,(i*j)%2019);
      }
    }
    cout<<result<<endl;
  }
  return 0; 
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<cctype>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);i++)
#define reps(i,n) for (int i=1;i<=(n);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rreps(i,n) for (int i=(n);i>0;i--)
#define all(v) (v).begin(),(v).end()
#define pi 3.1415926535897932384
#define E9 1000000000
#define eps 1e-4
#define pii pair<int,int>
template<class T> inline bool chmin(T &a, T b) {if (a>b) {a = b; return 1;} return 0;};
template<class T> inline bool chmax(T &a, T b) {if (a<b) {a = b; return 1;} return 0;};
typedef long long int ll;
const long long INF = 1LL << 60;

int main(){
  int N; cin >> N;
  ll A[N]; rep(i,N) cin >> A[i];
  ll cumsum = 0;
  map<ll,int> d;
  d[0]++;
  rep(i,N){
    cumsum += A[i];
    d[cumsum]++;
  }
  ll ans = 0;
  for (auto p:d){
    ll n = p.second;
    ans += n*(n-1)/2;
  }
  cout << ans << endl;
 

  // cout << fixed << setprecision(10);
  
  return 0;
}


Measured memory_bytes: 17660
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>
#include <functional>
#include <iomanip>

using namespace std;

//#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ;
#endif

#define EPS (1e-10)
#define equals(a,b) (fabs((a)-(b)) < EPS)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N; cin >> N;
    VI a(N);
    map<int,LL> mpcnt;
    map<int,LL> mparg;
    LL sum = 0;
    REP(i,N){
        cin >> a[i];
        mpcnt[a[i]]++;
        if(mparg[a[i]] != 0){
            mparg[a[i]] = min(mparg[a[i]],LL(i+1));
        }else{
            mparg[a[i]] = i+1;
        }
        sum += a[i];
    }
    VL ans(N+1);

    for(auto itr = mpcnt.end(); itr != next(mpcnt.begin(),1); itr--){
        auto pitr = prev(itr,1);
        auto qitr = prev(itr,2);
        dump(pitr->first)
        dump(pitr->second)
        dump(qitr->first)
        dump(qitr->second)


        ans[mparg[pitr->first]] += pitr->second * (pitr->first - qitr->first);
        //cout << "num:" << mparg[pitr->first] << endl;
        //cout << "add:" << pitr->second * (pitr->first - qitr->first) << endl;


        qitr->second += pitr->second ;
        mparg[qitr->first] = min(mparg[qitr->first],mparg[pitr->first]);


        //if(itr == next(mpcnt.begin(),2)){

        //}
    }
    FOR(i,1,N+1){
        sum -= ans[i];
    }
    ans[1] += sum;

    FOR(i,1,N+1){
        cout << ans[i] << endl;
    }



}


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

int main() {
  int n;
  cin >> n;
  set<string> prizes;
  rep(i,n) {
    string prize;
    cin >> prize;
    prizes.insert(prize);
  }
  cout << prizes.size() << endl;
  return 0;
}

Measured memory_bytes: 19200
#include<iostream>
#include<iomanip>
#include<fstream>
#include<sstream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cwchar>
#include<cwctype>
#include<exception>
#include<locale>
#include<numeric>
#include<new>
#include<stdexcept>
#include<limits>
#include<valarray>
#include<set>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<map>
#include<list>
#include<utility>
#include<bitset>
#include<algorithm>
#include<functional>
using namespace std;
int main()
{
	int n,a,b;
	cin>>n>>a>>b;
	cout<<min(n*a,b);
	return 0;
}

Measured memory_bytes: 256
sx, sy, tx, ty = map(int, input().split())

w = tx - sx
h = ty - sy

loop1 = 'U' * h + 'R' * w + 'D' * h + 'L' * w
loop2 = 'L' + 'U' * (h+1) + 'R' * (w+1) + 'D' + 'R' + 'D' * (h+1) + 'L' * (w+1) + 'U'
print(loop1 + loop2)

Measured memory_bytes: 3060
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <bitset>
#include <functional>
#include <numeric>
#include <ctime>
#include <cassert>
#include <cstring>
#include <fstream>
 
using namespace std;
int main(){
int N,X;
cin>>N>>X;
int S=0;
int a=1000;
for (int i=0;i<N;i++){
int m;
cin>>m;
S+=m;
a=min(a,m);
}
cout<<N+(X-S)/a<<endl;
}

Measured memory_bytes: 256
import java.util.*;
import java.math.BigDecimal;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        String ans = "NG";
        
        for(int i=a; i<=b; i++){
            if(i%k == 0){
                ans = "OK";
                break;
            }
        }
        
        System.out.println(ans);
    }
}

Measured memory_bytes: 35820
#include<iostream>
#include<vector>
#include<queue>
using namespace::std;

vector<pair<int,int>> v[105];
int visited[105][105];
bool vis[105][105];

int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			visited[i][j]=1e9;
	for(int i=0,l,r,w;i<m;i++)
		cin>>l>>r>>w,v[l].push_back({w,r}),v[r].push_back({w,l});
		
	priority_queue<pair<int,pair<int,pair<int,int>>>,vector<pair<int,pair<int,pair<int,int>>>>,greater<pair<int,pair<int,pair<int,int>>>>> q;
	for(int i=1;i<=n;i++){
		visited[i][i]=0;
		q.push({0,{i,{0,0}}});
		while(!q.empty()){
			int a=q.top().second.first,b=q.top().first;
			pair<int,int> edge=q.top().second.second;q.pop();
			if(visited[i][a]==b)
				vis[edge.first][edge.second]=1;
				
			for(auto g:v[a])
				if(visited[i][g.second]>visited[i][a]+g.first)
					q.push({visited[i][g.second]=visited[i][a]+g.first,{g.second,{a,g.second}}});
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			ans+=(vis[i][j]||vis[j][i]);
	cout<<m-(ans)<<'\n';
}

Measured memory_bytes: 384
print([1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51][int(input())-1])

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

int main() {
  int n,k; cin >> n >> k;
  int l[n];
  REP(i,n) cin >> l[i];
  sort(l,l+n, greater<int>());
  int ans=0;
  REP(i,k) ans+=l[i];
  cout << ans << endl;
  return 0;
}


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

class Dice {
public:
	int dice[6];
};


int check(Dice d1,Dice d2){
	for(int i=0;i<4;i++){
        int tmp1=d1.dice[0];
        d1.dice[0]=d1.dice[2], d1.dice[2]=d1.dice[5], d1.dice[5]=d1.dice[3], d1.dice[3]=tmp1;
        for(int j=0;j<4;j++){
            int tmp2=d1.dice[0];
            d1.dice[0]=d1.dice[1], d1.dice[1]=d1.dice[5], d1.dice[5]=d1.dice[4], d1.dice[4]=tmp2;
            for(int k=0;k<4;k++){
                int tmp3=d1.dice[1];
                d1.dice[1]=d1.dice[2], d1.dice[2]=d1.dice[4], d1.dice[4]=d1.dice[3], d1.dice[3]=tmp3;
				for(int i = 0; i < 6; i++){
					if(d1.dice[i] != d2.dice[i]){
						i = 6;
					}
					if(d1.dice[i] == d2.dice[i] and i == 5){
						return 1;
					}
                }
            }
        }
    }
	return -1;
}

int main(){
	int n;
	cin >> n;
	Dice di[n];
	for(int i = 0; i < n; i++){
		for(int j = 0; j < 6; j++){
			cin >> di[i].dice[j];
		}
	}
	int eck = 0;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < 6; j++){
			if(i != j) {
				int ch = check(di[i],di[j]);
				if(ch == 1) eck = 1;
			}
		}
	}
	if( eck == 1 ) cout << "No" << endl;
	else cout << "Yes" << endl;
	return 0;
}     

Measured memory_bytes: 3096
from sys import stdin


def main() -> None:
    a = next_int()
    b = next_int()

    print(("Negative", "Zero", "Positive")[calc(a, b) + 1])


def calc(a: int, b: int) -> int:
    if a <= 0 <= b:
        return 0
    elif a > 0 or (b - a) % 2 != 0:
        return 1
    else:
        return -1


def next_int() -> int:
    return int(next_str())


def next_str() -> str:
    result = ""
    while True:
        tmp = stdin.read(1)
        if tmp.strip() != "":
            result += tmp
        elif tmp != '\r':
            break
    return result


if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
#include<stdio.h>
int main(void){
	int a, b, c, d;
	double a2, b2, e;
	scanf("%d%d", &a, &b);
	c = a / b;
	d = a % b;
	a2 = a;
	b2 = b;
	e = a2 / b2;
	printf("%d %d %f\n", c, d, e);
	return 0;
}

Measured memory_bytes: 636
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp> //required
// #include <ext/pb_ds/tree_policy.hpp> //required
// using namespace __gnu_pbds; //required 
using namespace std;

#define ll long long 
#define loop(x) for(int i=0;i<x;i++)

#define llu unsigned long long 
#define pb push_back
#define sc(x) scanf("%lld",&x)
#define pr(x) printf("%lld\n",x)
#define dd fflush(stdout)
#define what_is(x) cerr << #x << " is " << x << endl;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define mt make_tuple //use tie
#define eb emplace_back
typedef tuple<int,int,int> State;//use in dijkstra
ll mod=1e9+7;
// ll power(ll x,ll y,ll mod){
//  ll ans=1;
//  while(y>0){
//   if(y&1){
//     ans=ans*x;
//   }
//   x=x*x;
//   y=y/2;
//  }
//  return ans;
// }

// typedef tree<
// pair<int, int>,
// null_type,
// less<pair<int, int>>,
// rb_tree_tag,
// tree_order_statistics_node_update> ordered_set;
 vector<int>v[100005];
 ll dp[100005][4];
 int visited[100005];
  int n;
 void dfs(int start){
   
   visited[start]=1;
   int flag=0;
   ll val1=1;
   ll val2=1;
   for(int i=0;i<v[start].size();i++){
          int z=v[start][i];
     if(visited[z]==0)
     {dfs(z);
      flag=1;
      val1=(val1*(dp[z][0]+dp[z][1]))%mod;
      val2=(val2*dp[z][0])%mod;
     }
   }
   if(flag==0){
    dp[start][0]=1;
    dp[start][1]=1;
   }
   else{
    dp[start][0]=val1;
    dp[start][1]=val2;
   }
 }
int main(){
    IOS;  
  
   cin>>n;
   memset(visited,0,sizeof visited);
   int x,y;
   loop(n-1){
    cin>>x>>y;
    v[x].pb(y);
    v[y].pb(x);
   } 
   memset(dp,0,sizeof dp);
   dfs(1);
   cout<<((dp[1][1]+dp[1][0])%mod)<<endl; 
   
 }
// https://atcoder.jp/contests/dp/tasks/dp_d
// https://codeforces.com/contest/1131/problem/C
 
//csjosh


Measured memory_bytes: 16256
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MOD 1000000007
#define INF (1<<30)
#define LINF (1LL<<60)
#define endl "\n"
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
typedef unsigned long long int ull;
typedef long long lint;
 
int main(void){
  int N;
  cin >> N;
  for(int i=1;i<10;i++){
    if(i*111>=N){
      cout << i*111 << endl;
      break;
    }
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
typedef pair<ll,ll>P;
vector<P>vec;
vector<P>v;
bool f[100009],g[100009];

int main(){
  ll n,k;
  cin>>n>>k;
  for(int i=0;i<n;i++){
    ll t,d;
    cin>>t>>d;
    vec.push_back(P(d,t));
  }
  sort(vec.begin(),vec.end());
  reverse(vec.begin(),vec.end());

  ll p=0,sum=0;
  for(int i=0;i<k;i++){
    ll d=vec[i].fi;
    ll t=vec[i].se;
    if(!f[t]){
      g[i]=true;
      f[t]=true;
      p++;
    }
    sum+=d;
  }

  for(int i=k;i<n;i++){
    ll d=vec[i].fi;
    ll t=vec[i].se;
    if(!f[t]){
      v.push_back(vec[i]);
      f[t]=true;
    }
  }

  ll cnt=0,ans=sum+p*p;
  for(int i=k-1;i>=0;i--){
    ll d=vec[i].fi;
    ll t=vec[i].se;
    if(g[i]||cnt>=v.size())continue;
    sum=sum-d+v[cnt].fi;
    p++;
    ans=max(ans,sum+p*p);
    cnt++;
  }

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


Measured memory_bytes: 3824
#include<stdio.h>
#include<algorithm>
#include<set>
using namespace std;
int p[110000];
set<int>S;
set<int>T;
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++)scanf("%d",p+i);
	int M=0;
	int ke=0;
	long long pat=0;
	int best=0;
	for(int i=a-1;i>=0;i--){
		int t=M-p[i];
	//	printf("%d %d\n",M,t);
		if(best<t){
			pat=ke;
			best=t;
		}else if(best==t){
			pat+=ke;
		}
		
		if(M==p[i])ke++;
		if(M<p[i]){
			ke=1;
			M=p[i];
		}
	}
//	printf("%d\n",best);
	int A=0;
	int B=0;
	for(int i=0;i<a;i++){
		if(S.count(p[i]-best))A++;
		S.insert(p[i]);
	}
	for(int i=a-1;i>=0;i--){
		if(T.count(p[i]+best))B++;
		T.insert(p[i]);
	}
	printf("%d\n",min(A,B));
}

Measured memory_bytes: 9984
#include<iostream>
using namespace std;
int m,n,ans=0;
string a;
int main(){
	cin>>n;
	cin>>a;
	char b;
	b=a[0];
	ans++;
	for(int i=1;i<a.size();i++){
		if(a[i]!=b){
			ans++;
			b=a[i];
		}
	}
	cout<<ans<<endl;
	return 0; 
} 

Measured memory_bytes: 1144
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
 
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <iterator>
#include <functional>
#include <limits>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <stack>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
typedef long long int ll;
 
#define endl '\n'
#define int ll

ll mod=1e9+7;
ll mod1=1e9+5;
ll power(ll a,ll b)
{
    if(b==0) return 1;
    else if(b%2==0)
        return power((((a%mod)*(a%mod))%mod),b/2)%mod;
    else return ((a%mod)*(power((((a%mod)*(a%mod))%mod),b/2)%mod))%mod;
}
int n,a[21][21],dp[21][1<<21];
int solve(int w,int mask)
{
    if(w==n)
        return 1;
    int &res=dp[w][mask];
    if(res!=-1)
    {
        return res;
    }
    res=0;
    for(int i=0;i<n;++i)
    {
        if(a[w][i]!=0 && ((mask&(1<<i))&&1)==0)
        {
            res+=solve(w+1,mask|1<<i);
            res=res%mod;
        }
    }
    return res;
}


int32_t main()
{
    IOS
    
    cin>>n;
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            cin>>a[i][j];
        memset(dp,-1,sizeof(dp));
    cout<<solve(0,0);
}



Measured memory_bytes: 344320
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++)
#define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define rreps(i,n) for(int i=((int)(n));i>0;i--)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define solve(a) ((a)?"Yes":"No")
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long , long long> P;
typedef vector<P> VP;
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;}
const long long INFLL = 1LL<<62;
const int INF = 1<<30;
const double PI=acos(-1);
int main(){
	int n;
	ll mod=1e9+7;
	string s;
	ll ans=1LL;
	cin >>n>>s;
	map<char,ll>box;
	for(int i=0;i<n;i++){
		box[s[i]]+=0LL;
		box[s[i]]++;
	}
	for(auto itr=box.begin();itr!=box.end();itr++){
		ans*=((itr->S)+1);
		ans%=mod;
	}
	ans+=mod-1;
	ans%=mod;
	cout<<ans<<endl;
}

Measured memory_bytes: 512
#include <stdio.h>

int main(){

  int W, H, x, y, r;

  scanf("%d %d %d %d %d", &W, &H, &x, &y, &r);

  if(x <= 0 || y <= 0 || x > W - r || y > H - r)
    printf("No\n");
  else
    printf("Yes\n");

  return 0;
}

Measured memory_bytes: 584
n = int(input())
a = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))
lst = set()
for i in a:
    templ = list(lst)
    for j in templ:
        lst.add(i+j)
    lst.add(i)
for i in m:
    if i in lst:
        print('yes')
    else:
        print('no')
        


Measured memory_bytes: 5648
ss = [0] + gets.chomp.split('').map{|c|c == 'A' ? 1 : -1}
ts = [0] + gets.chomp.split('').map{|c|c == 'A' ? 1 : -1}

(ss.length-1).times do |i|
    ss[i+1] += ss[i]
end
(ts.length-1).times do |i|
    ts[i+1] += ts[i]
end

q = gets.to_i
q.times do
    a, b, c, d = gets.split.map(&:to_i)
    if (ss[b] - ss[a-1] - ts[d] + ts[c-1]) % 3 == 0
        puts 'YES'
    else
        puts 'NO'
    end
end


Measured memory_bytes: 20952
import java.util.*;
import java.io.*;

public class Main {
	static final long MOD = 1000000007;
	public static void main (String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] first = br.readLine().split(" ", 2);
		int n = Integer.parseInt(first[0]);
		long k = Integer.parseInt(first[1]);
		ArrayList<Integer>[] tree = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			tree[i] = new ArrayList<Integer>();
		}
		for (int i = 0; i < n - 1; i++) {
			String[] line = br.readLine().split(" ", 2);
			int a = Integer.parseInt(line[0]) - 1;
			int b = Integer.parseInt(line[1]) - 1;
			tree[a].add(b);
			tree[b].add(a);
		}
		boolean[] visited = new boolean[n];
		ArrayList<Integer> now = new ArrayList<>();
		now.add(0);
		long ans = k;
		boolean isfirst = true;
		while (true) {
			ArrayList<Integer> next = new ArrayList<>();
			for (int x : now) {
				if (isfirst) {
					for (int i = 0; i < tree[x].size(); i++) {
						ans *= k - 1 - i;
						ans %= MOD;
					}
				} else {
					for (int i = 0; i < tree[x].size() - 1; i++) {
						ans *= k - 2 - i;
						ans %= MOD;
					}
				}
				visited[x] = true;
				for (int y : tree[x]) {
					if (!visited[y]) {
						next.add(y);
					}
				}
			}
			isfirst = false;
			if (next.size() == 0) {
				break;
			}
			now = next;
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 63088
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

int n_query = 0;

int ask(int y1, int x1, int y2, int x2)
{
	++n_query;
	printf("? %d %d %d %d\n", y1, x1, y2 - 1, x2 - 1);
	fflush(stdout);
	int a;
	scanf("%d", &a);
	return a;
}

int score(int q)
{
	if (q > 2500) return 0;
	if (q >= 930) return max((int)(1e-8 + 125 - 3.2 * sqrt(q - 920)), 40);
	if (q >= 880) return (int)(1e-8 + 288 - 22 * sqrt(q - 870));
	return min(2860 - 3 * q, 300);
}

int H, W, N, K;
int C[50][50];

void solve(int y1, int x1, int y2, int x2, int cnt)
{
	if (y2 - y1 == 1 && x2 - x1 == 1) {
		C[y1][x1] = cnt;
		return;
	}
	if (cnt == 0) return;
	if ((y2 - y1) * (x2 - x1) == cnt) {
		for (int i = y1; i < y2; ++i) {
			for (int j = x1; j < x2; ++j) {
				C[i][j] = 1;
			}
		}
		return;
	}

	if (x2 - x1 == 1) {
		int ym = (y2 + y1) / 2;
		int a = ask(y1, x1, ym, x2);
		solve(y1, x1, ym, x2, a);
		solve(ym, x1, y2, x2, cnt - a);
	} else {
		int xm = (x2 + x1) / 2;
		int a = ask(y1, x1, y2, xm);
		solve(y1, x1, y2, xm, a);
		solve(y1, xm, y2, x2, cnt - a);
	}
}

int main()
{
	scanf("%d%d%d%d", &H, &W, &N, &K);
	solve(0, 0, H, W, N);

	int ret = 0;
	int pw = 1;
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			ret += C[i][j] * pw;
			ret %= K;
			pw = pw * 2 % K;
		}
	}
	int aa = ask(15, 15, 35, 45);
	while (score(n_query) > aa) ask(0, 0, 1, 1);

//	if (aa != 69 && aa != 76 && aa != 78 && aa != 59 && aa != 63) return 0;

	printf("! %d\n", ret);
	return 0;
}


Measured memory_bytes: 592
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int I[20][20];
int D[405][405];
int main() {
  ios::sync_with_stdio(false);
  int H, W;
  string S[20];
  cin >> H >> W;
  for (int i=0; i<H; i++) {
    cin >> S[i];
  }
  int N = 1;
  for (int i=0; i<H; i++) {
    for (int j=0; j<W; j++) {
      if (S[i][j] == '.') {
        I[i][j] = N++;
      }
    }
  }
  int INF = 100000;
  for (int i=0; i<N; i++) {
    for (int j=0; j<N; j++) {
      D[i][j] = INF;
    }
  }
  for (int i=0; i<H; i++) {
    for (int j=0; j<W; j++) {
      if (S[i][j] == '.') {
        int k = I[i][j];
        D[k][k] = 0;
        if (i > 0) { int l = I[i-1][j]; D[k][l] = D[l][k] = 1; }
        if (j > 0) { int l = I[i][j-1]; D[k][l] = D[l][k] = 1; }
        if (i < H-1) { int l = I[i+1][j]; D[k][l] = D[l][k] = 1; }
        if (j < W-1) { int l = I[i][j+1]; D[k][l] = D[l][k] = 1; }
      }
    }
  }
  for (int k=1; k<N; k++) {
    for (int i=1; i<N; i++) {
      for (int j=1; j<N; j++) {
        D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
      }
    }
  }
  int ret = 0;
  for (int i=1; i<N; i++) {
    for (int j=1; j<N; j++) {
      if (D[i][j] < INF) {
        ret = max(ret, D[i][j]);
      }
    }
  }
  cout << ret << endl;
}

Measured memory_bytes: 896
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <functional>
#include <map>
#include <set>
#include <stack>
#include <deque>

#define INF 1000000000;
#define MOD 1000000007;
#define LIMIT 1000000000000000000;
typedef long long ll;
using namespace std;
typedef pair<int, int> P;

int main()
{
    int N, K; cin >> N >> K;
    vector<int> xs(N);
    for (int i = 0; i < N; i++) {
        int x; cin >> x;
        xs[i] = x;
    }

    int ans = INF;
    for (int i = 0; i <= N - K; i++) {
        int left = xs[i];
        int right = xs[i + K - 1];
        if (left >= 0 && right >= 0) {
            ans = min(ans, right);
        }
        else if (left < 0 && right >= 0) {
            int l_back = abs(left * 2) + right;
            int r_back = abs(left) + (right * 2);
            ans = min(ans, min(l_back, r_back));
        }
        else if (left < 0 && right < 0) {
            ans = min(ans, abs(left));
        }
    }

    cout << ans << endl;
}

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

int main()
{
    int a[6], tmp = 0, ind = 0;
    for(int i = 0; i < 5; i++)
    {
        cin >> a[i];
        if(!i)
        {
            ind = 0;
            tmp = a[0];
        }
        if(a[i] % 10 != 0 && a[i] % 10 < tmp % 10)
        {
            ind = i;
            tmp = a[i];
        }
    }
    int sum = 0;
    for(int i = 0; i < 5; i ++)
    {
        if(i != ind)
        {
            if(a[i] % 10 != 0)
                a[i] += 10- a[i]%10;
        }
        sum += a[i];
    }
    cout << sum;
}



Measured memory_bytes: 256
import java.util.Scanner;

class Main {

    static int[] L = new int[200000 / 2 + 2];
    static int[] R = new int[200000 / 2 + 2];

    private static long merge(int A[], int l, int m, int r){
        int n1 = m-l;
        int n2 = r-m;
        long count = 0;

        for (int i = 0; i < n1; i++)
            L[i] = A[l+i];
        for (int i = 0; i < n2; i++)
            R[i] = A[m+i];

        L[n1] = 2000000000;
        R[n2] = 2000000000;

        int i = 0, j = 0;
        for (int k = l; k < r; k++) {
            if (L[i] <= R[j]){
                    A[k] = L[i++];
            }
            else{
                count += n1-i;
                A[k] = R[j++];
            }
        }
        return count;

    }

    private static long sort(int A[], int l, int r){
        long sum = 0;

        if (l + 1 < r ){
            int mid = (l + r) / 2;
            sum += sort(A, l, mid);
            sum += sort(A, mid, r);
            sum += merge(A, l, mid, r);
        }

        return sum;
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] a = new int[n];

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

        System.out.println(sort(a,0, n));
    }
}



Measured memory_bytes: 103292