akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <limits.h>
#include <math.h>
#include <functional>
#include <bitset>
#include <iomanip>
#include <cassert>

#define repeat(i,n) for (long long i = 0; (i) < (n); ++ (i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i] << '\n'
#define debugArrayP(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i].first<< " " << x[i].second << '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef vector<int> vint;
typedef vector<ll> vll;
const ll INF = INT_MAX;
const ll MOD = 1e9+7;

int N,W;
ll w[112],v[112];
ll dp[112345];

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin>>N>>W;
  repeat(i,N){
    cin>>w[i]>>v[i];
  }
  fill(dp,dp+100010,INF);
  dp[0]=0;
  repeat(i,N){
    for(int j=100000;j>=v[i];j--){
      if(dp[j-v[i]]!=INF)dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
    }
  }
  ll ans = 0;
  repeat(j,100010){
    if(dp[j]<=W){
      ans = j;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
const ll mod = 1000000007;
int n;
ll x[100005],y[100005];
vector<int>vec[200005];
vector<ll>za;
struct BIT
{
	int bit[200005];
	int f(int x)
	{
		return x&-x;
	}
	void add(int i,int x)
	{
		i++;
		for(int s=i;s<200005;s+=f(s)) bit[s]=max(bit[s],x);
	}
	int sum(int i)
	{
		i++;
		int res=0;
		for(int s=i;s>0;s-=f(s)) res=max(res,bit[s]);
		return res;
	}
}kaede;

int main(){
	cin >> n;
	rep(i,n){
		ll p,q;
		cin >> p >> q;
		x[i] = p-q;
		y[i] = p+q;
		za.pb(x[i]); za.pb(y[i]);
	}
	SORT(za); ERASE(za);
	rep(i,n){
		x[i] = POSL(za,x[i]);
		y[i] = POSL(za,y[i]);
		vec[x[i]].pb(y[i]);
	}
	rep(i,za.size()){
		int val = kaede.sum(i);
		rep(j,vec[i].size()){
			kaede.add(vec[i][j],val+1);
		}
	}
	cout << kaede.sum(za.size()-1) << endl;
}

Measured memory_bytes: 12016
#include<bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
#define mod 1000000007
#define mod2 998244353 
#define PI 3.14159265
#define ll long long
#define ld long double
#define pi pair<ll,ll>
#define pb push_back
#define vi vector<ll>
#define sz size()
#define setbits(x)  __builtin_popcount(x)
#define fi first
#define se second
#define lz length()
#define all(x) (x).begin(),(x).end()
#define scf(x) scanf("%lld",&x)
#define rep(i,n) for(ll i=0;i<n;i++)
const int INF = (int)1e9;
const ll IINF=1LL<<62;
const int maxn=10000005;

//int divr[maxn];
/**/
/*void divisor()
{for(int i=2;i<sqrt(maxn);i++)
     {
          if(!divr[i])
          {
               for(int j=i*i;j<maxn;j+=i)if(!divr[j])divr[j]=i;     
          }
     }
     for(int i=1;i<maxn;i++)if(!divr[i])divr[i]=i;
}*/
 
/*const int N=1000005;
ll n;
struct line {
    long long m, c;
    long long eval(long long x) { return m * x + c; }
    long double intersectX(line l) { return (long double) (c - l.c) / (l.m - m); }
};
vector<pair<pi,ll>> rect;
deque<line> dq;
*/
ll modexpo(ll a,ll b)
{
     ll ans=1LL;
     while(b>0)
     {
          if(b&1)ans=(ans*a)%mod;
          a=(a*a)%mod;
          b>>=1;
     }
     return ans;
}
 
 
 
 
 
 
 


int px[90001],py[90001];
ll dt[90001];
int main()
{
     int h,w,d;
     cin>>h>>w>>d;
     for(int i=0;i<h;i++){
          for(int j=0;j<w;j++){
              int x;cin>>x;
              px[x]=i+1;
              py[x]=j+1;
          }
     }
     for(int i=d+1;i<=h*w;i++){
          dt[i]=dt[i-d]+abs(px[i]-px[i-d])+abs(py[i]-py[i-d]);
     }
     int q;
     cin>>q;
     while(q--){
          int l,r;
          cin>>l>>r;
          cout<<dt[r]-dt[l];
          cout<<"\n";
     }


}























Measured memory_bytes: 4948
#include "bits/stdc++.h"
using namespace std;

#define ASC(vec) vec.begin(), vec.end()    // 昇順ソート 例：sort(ASC(vec));
#define DESC(vec) vec.rbegin(), vec.rend() // 降順ソート 例：sort(DESC(vec));
#define rep(i, n) for (int i = 0; i < (n); i++)
#define Rep(i, n) for (int i = 1; i < n; i++)
#define REP(i, vec) for (auto i = vec.begin(); i != vec.end(); ++i)

const int       mod = 1000000007;
const int       inf = (1 << 21);
const long long INF = 1LL << 60;

using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
using vd = vector<double>;
using vb = vector<bool>;
using vl = vector<ll>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvb = vector<vector<bool>>;
using vii = vector<pair<int, int>>;
using vll = vector<pair<ll, ll>>;

template<class T>
inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T>
inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T>
T GCD(T a, T b) { if (b == 0) return a; else return GCD(b, a % b); }
template<class T>
T LCM(T a, T b) { return a / GCD(a, b) * b; }

constexpr array<int, 9> dx = { 0, 1, 0, -1, -1, 1, 1, -1, 0 };
constexpr array<int, 9> dy = { 1, 0, -1, 0, 1, 1, -1, -1, 0 };

// ──────────────────────────────────────────────────────────────────

int main() {
	int a, n, m;
	cin >> a >> n >> m;

	int ans = 0;
	for (int ya = 1; ya <= 1000; ++ya) {
		ll x = pow(ya, n);

		if (x > m) break;

		int sum = 0;
		while (x) {
			sum += x % 10;
			x /= 10;
		}

		if (sum == ya - a) ans++;
	}
	cout << ans << endl;
}


Measured memory_bytes: 3264
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int main(){

	string s;
	int a, b, cha, sta, ma=-9;
	vector< vector<int> > board;

	cin>> a >> b;
	a+=2;
	b+=2;

	board.resize(a);
	for(int i=0;i<a;i++) board[i].resize(b);

	for(int i=0;i<a;i++){
		board[i][0]=-9;
		board[i][b-1]=-9;
	}
	for(int i=0;i<b;i++){
		board[0][i]=-9;
		board[a-1][i]=-9;
	}

	for(int i=0;i<a-2;i++){
		cin>> s;
		for(int j=0;j<b-2;j++){
			if(s[j]=='#') board[i+1][j+1]=-9;
			else board[i+1][j+1]=0;
		}
	}

	for(int i=0;i<a;i++){
		cha=0;
		for(int j=0;j<b;j++){
			if(board[i][j]==0){
				if(cha==0) sta=j;
				cha++;
			}else{
				if(0<cha){
					for(int k=sta;k<j;k++) board[i][k]+=cha;
					cha=0;
				}
			}
		}
	}

	for(int j=0;j<b;j++){
		cha=0;
		for(int i=0;i<a;i++){
			if(0<=board[i][j]){
				if(cha==0) sta=i;
				cha++;
			}else{
				if(0<cha){
					for(int k=sta;k<i;k++) board[k][j]+=cha;
					cha=0;
				}
			}
		}
	}

	for(int i=0;i<a;i++){
		for(int j=0;j<b;j++){
			ma=max(ma, board[i][j]);
		}
	}

	/*for(int i=0;i<a;i++){
		for(int j=0;j<b;j++){
			cout<< board[i][j] << " ";
		}
		cout<< endl;
	}*/

	cout<< ma-1 << endl;

}

Measured memory_bytes: 16000
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class AtCoderA
{
    static void Main()
    {
        var sc = new Scanner();

        int a = sc.NextInt();
        int b = sc.NextInt();
        int c = sc.NextInt();
        int d = sc.NextInt();
        int e = sc.NextInt();
        int k = sc.NextInt();

        string answer = e - a <= k ? "Yay!" : ":(";

        Console.WriteLine(answer);
    }

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}

Measured memory_bytes: 13140
#include <bits/stdc++.h>
#include <stdint.h>
#include <algorithm>

using namespace std;

int main() {
	int N,Q;
	cin >> N >> Q;
	string S;
	cin >> S;
	
	vector<int> ac(S.size()+1,0);
	for (int i = 0; i < S.size()-1; i++) {
		ac.at(i+1) = ac.at(i);
		if((S.at(i) == 'A') && (S.at(i+1) == 'C')) {
			ac.at(i+1)++;
		}
		
	}

/*
for (int i = 0; i < ac.size(); i++) {
	cout << ac.at(i) << " ";
}
cout << endl;
*/

	
	int l,r;
	int ans = 0;
	for ( int i = 0; i < Q; i++) {
		cin >> l >> r;
		ans = ac.at(r-1) - ac.at(l-1);
		
		cout << ans << endl;
		ans = 0;
	}
		
		
		
	return 0;
}


Measured memory_bytes: 1408
#include<stdio.h>
#include<math.h>
#include<stdlib.h>

#define MAX 362880
#define N 3
#define N2 9

typedef struct puzzle{
  int f[N2];
  int space;
  int path;
}puzzle;

static const int dx[4] = {-1, 0, 1, 0};
static const int dy[4] = {0, -1, 0, 1};

puzzle Q[MAX];
int head, tail, V[MAX];

int empty()
{
  return head == tail;
}

void enqueue(puzzle x)
{
  Q[tail] = x;
  tail = (tail+1)%MAX;
}

puzzle front()
{
  puzzle x;

  x = Q[head];
  head = (head+1)%MAX;

  return x;	
}

int cheak(puzzle p)
{
  int i, j, fac, count, res = 0;

  for(i = 0, fac = 1; i < N2; fac*= ++i){
    for(j = 0, count = 0; j < i; j++)
      if(p.f[j] < p.f[i])
	count++;
    res += count*fac;
  }
	
  return res;	
}

int isTarget(puzzle p)
{
  int i;

  for (i = 0; i < N2; i++)
    if(p.f[i] != (i + 1))
      return 0;
  return 1;
}

int bfs(puzzle s)
{
  int sx, sy, tx, ty, r, temp;
  puzzle u, v;
	
  s.path = 0;
  enqueue(s);
  V[cheak(s)] = 1;
  while(!empty()){
    u = front();
    if( isTarget(u))
      return u.path;
    sx = u.space / N;
    sy = u.space % N;
    for (r = 0; r < 4; r++){
      tx = sx + dx[r];
      ty = sy + dy[r];
      if(tx < 0 || ty < 0 || tx >= N || ty >= N)
	continue;
      v = u;		
      temp = v.f[u.space];
      v.f[u.space] = v.f[tx * N + ty];
      v.f[tx * N + ty] = temp;	
      v.space = tx * N + ty;
      if(!V[cheak(v)]){
	V[cheak(v)] = 1;
	v.path++;
	enqueue(v);
      }
    }
  }
	
  return -1;
}

int main()
{
  int i, a;
  puzzle p;
	
  for(i = 0; i < N2; i++){
    scanf("%d", &p.f[i]);
    if( p.f[i] == 0){
      p.f[i] = N2;
      p.space = i;
    }
  }
	
  a = bfs(p);
  printf("%d\n",a);
	
  return 0;
}



Measured memory_bytes: 11024
import java.util.*;

public class Main{

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        String s = sc.next();
        String pattern = "^[0-9]{" + a + "}-[0-9]{" + b + "}$";
        if(s.matches(pattern))System.out.println("Yes");
        else System.out.println("No");
        sc.close();
    }

}

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

int main(){
    int N;
    cin >> N;
    vector<int> H(N);
    for(int i = 0; i < N; i++) cin >> H.at(i);
    bool check = true;
    for(int i = 0; i < N - 1; i++){
        if(H.at(N-1-i) >= H.at(N-2-i)) continue;
        else if(H.at(N-1-i) >= H.at(N-2-i) - 1) H.at(N-2-i)--;
        else {
            check = false;
            break;
        }
    }
    if(check) cout << "Yes" << endl;
    else cout << "No" << endl;

}

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

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

const int INF = 100000001;

int main() {
    int n,m;cin>>n>>m;
    
    vector<int>to[100001];
    
    int t1,t2;
    
    rep(i,m){
        cin>>t1>>t2;
        t1-=1;t2-=1;
        
        to[t1].push_back(t2);
        to[t2].push_back(t1);
    }
    
    queue<int> q;
    vector<int> dist(n,INF);
    vector<int> pdis(n, -1);
    
    dist[0]=0;
    q.push(0);
    while(!q.empty()){
        int v = q.front(); q.pop();
        for(int u : to[v]){
            if (dist[u] != INF) continue;
            dist[u] = dist[v]+1;
            pdis[u] = v;
            q.push(u);
        }
    }
    
    cout<<"Yes"<<endl;
    
    rep(i,n){
        if(i==0) continue;
      int ans = pdis[i]; ans++;
        cout<<ans<<endl;
    }
	return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<pdd> vdd;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define mem(a,b) memset(a, b, sizeof(a) )
#define all(x) (x).begin(),(x).end()
#define INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }

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

int main(){
    int n;
    cin>>n;
    vi a(n),b(n),c(n);rep(i,n)cin>>a[i]>>b[i]>>c[i];
    int dp[100005][3];
    dp[0][0]=0;dp[0][1]=0;dp[0][2]=0;
    for(int i=0;i<n;++i){
        dp[i+1][0]=max(dp[i][1],dp[i][2])+a[i];
        dp[i+1][1]=max(dp[i][0],dp[i][2])+b[i];
        dp[i+1][2]=max(dp[i][0],dp[i][1])+c[i];
    }
    cout<<max({dp[n][0],dp[n][1],dp[n][2]});
}

Measured memory_bytes: 2560
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime> 
#include <memory.h>
#include <assert.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
const int INF = 1e9 + 1;
const ll LLINF = 1e18 + 1;

int main() {
    ll N, M, C;
    cin >> N >> M >> C;
    vector<ll> B(M);
    for(int i = 0; i < M; i++) cin >> B[i];
    vector<vector<ll> > A(N, vector<ll>(M));
    for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) cin >> A[i][j];

    ll ans = 0;
    for(int i = 0; i < N; i++) {
        ll s = 0;
        for(int j = 0; j < M; j++) {
            s += B[j] * A[i][j];
        }
        s += C;
        if(s > 0) ans++;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <array>
#include <queue>
#include <deque>
#include <set>
#include <list>
#include <map>
#include <stack>
#include <utility>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <bitset>
#include <random>
#include <functional>
#include <sstream>
#include <iomanip>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); i++)
#define FOR(i, m, n) for(int i=(m);i<(n);i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort((x).begin(),(x).end())
#define REVE(x) reverse((x).begin(),(x).end())
#define mp make_pair
#define pb push_back

typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<bool> VB;

int main() {
	int d, g;
	cin >> d >> g;
	VI s(d), p(d), c(d);
	rep(i, d) {
		cin >> p[i] >> c[i];
		s[i] = (i + 1) * 100;
	}

	VI cmp(d);
	rep(i, d)cmp[i] = s[i] * p[i] + c[i];


	int ans = INT_MAX;
	for (int bit = 0; bit < (1 << d); bit++) {

		int pro = 0, sco = 0;

		for (int i = 0; i < d; i++) {
			//cmp
			if (bit&(1 << i)) {
				pro += p[i];
				sco += cmp[i];
			}
		}

		if (sco < g) {

			for (int i = d - 1; i >= 0; i--) {
				int nokori = g - sco;
				if (!(bit&(1 << i))) {
					if (nokori < s[i] * (p[i] - 1)) {
						pro += (nokori + s[i] - 1) / s[i];
						sco += s[i] + (nokori + s[i] - 1) / s[i] * s[i];
						break;
					}
					else {
						pro += p[i] - 1;
						sco += (p[i] - 1)*s[i];
					}
				}
			}

		}
		//cout << bit << ":score->" << sco << " pro->" << pro << endl;

		if (sco >= g&&ans > pro)ans = pro;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
S = ['.'*(W + 2), *['.' + INPUT() + '.' for _ in range(H)], '.'*(W + 2)]

ans = ["" for _ in range(H)]
dy = [0, -1, -1, -1, 0, 1, 1, 1]
dx = [1, 1, 0, -1, -1, -1, 0, 1]
for i in range(H):
    for j in range(W):
        if S[i+1][j+1] == '#':
            ans[i] += '#'
            continue

        cnt = 0
        for y, x in zip(dy, dx):
            if S[i+1+y][j+1+x] == '#':
                cnt += 1

        ans[i] += str(cnt)

print(*ans, sep='\n')


Measured memory_bytes: 10376
#pragma GCC optimize("O3")
#include <string>
#include <algorithm>
int i;
#define rep2(i, a, b) for(i = a; i <= b; ++i)
#define rep(i, n) for(i = 0; i < n; ++i)
using namespace std;
// _________コーディングはここから！！___________
template <const int sz = 5 * 10000000, typename T = long long> struct IO {
    char reader[sz], writer[sz];
    char *now, *now2 = writer;
    IO() {
        reader[fread(reader, sizeof(char), sizeof(char) * sz, stdin)];
        now = reader;
    }
    inline T read() {
        while(*now && *now <= 32) now++;
        if(*now == '-') {
            now++;
            T res = 0;
            while('0' <= *now and *now <= '9') { res = res * 10 + *now++ - '0'; }
            return -res;
        } else {
            T res = 0;
            while('0' <= *now and *now <= '9') { res = res * 10 + *now++ - '0'; }
            return res;
        }
    }
    inline string read_str() {
        string res;
        while(*now and *now != '\n' and *now != ' ') res += *now++;
        now++;
        return res;
    }
    inline void write(T x, char margin = ' ') {
        if(x == 0) {
            putchar('0');
            putchar(margin);
            return;
        }
        if(x < 0) {
            putchar('-');
            x = -x;
        }
        while(x) {
            *now2 = '0' + x % 10;
            now2++;
            x /= 10;
        }
        do {
            now2--;
            putchar(*now2);
        } while(now2 != writer);
        putchar(margin);
    }
    inline void write_str(string s, char margin = ' ') {
        for(auto c : s) putchar(c);
        putchar(margin);
    }
};
IO io;
inline int read() { return io.read(); }
inline void write(int x) { io.write(x); }
inline void write(int x, char c) { io.write(x, c); }
constexpr int N = 500003;
int c[N];
struct T {
    int l, r, idx;
    constexpr bool operator<(const T &rhs) const noexcept { return r < rhs.r; }
} q[N];
int ans[N], last[N], dat[N];

inline void dec(int k) {
    for(++k; k < N; k += k & -k) --dat[k];
}
inline int sum(int k) {
    int res = 0;
    for(++k; k > 0; k -= k & -k) res += dat[k];
    return res;
}
int n, Q, now = 1;

// 頑張れ！！
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")
// 頑張れ！！

int main() {
    n = read(), Q = read();
    rep2(i, 1, n) c[i] = read();
    rep(i, Q) q[i].l = read(), q[i].r = read() + 1, q[i].idx = i;
    sort(q, q + Q);
    rep(i, Q) {
        for(; now < q[i].r; ++now) {
            if(last[c[now]]) dec(last[c[now]]);
            last[c[now]] = now;
        }
        ans[q[i].idx] = sum(q[i].r - 1) - sum(q[i].l - 1) + q[i].r - q[i].l;
    }
    rep(i, Q) write(ans[i], '\n');
}


Measured memory_bytes: 26772
D, N = map(int, input().split())

# if D = 0, any positive integer *NOT* divisible by 100, pick the N-th one
# if D = 1, any positive integer divisible by 100 exactly once, i.e. 100*range(N+1)
# if D = 2, any positive integer divisible by 100 exactly twice, i.e. 100*100*range(N+1)
def count_divisions(n):
    factors = 0
    while n%100 == 0:
        factors += 1
        n = n/100
    return factors
    
index = 0
number = 0
while index != N:
    number += 1
    if count_divisions(number) == D:
        index += 1
print(number)


Measured memory_bytes: 2940
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cstring>
#include<cmath>
#include <numeric>
#include<queue>
#include<climits>


#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
//#define INF ((LLONG_MAX) / (2))
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
typedef long long int ll;
typedef pair<ll,int> LL_IP;

#define INF 1e12+7
#define ARRAY_MAX 2010



typedef struct edge{
    ll from;
    ll to;
    ll cost;
}EDGE;



/*頂点sから各頂点への最短距離を求めること、頂点sから到達できる負閉路があれば真が返る、目的地が決まっているバージョン*/
/*V-1回の更新で各ノードへの最短距離は求められる*/
/*V回目から2V回目までに最短距離が更新される場合は目的地を含む負閉路が存在する*/
bool shortest_path(ll v,ll e,ll s,ll t,vector<EDGE>& arr,vector<ll>& d){
    /*頂点の個数、辺の個数、始点となる頂点、目的地の頂点、辺の情報、最短距離*/
    for(int i = 0;i < d.size();i++){
        d[i] = INF;
    }
    d[s]=0;
    
    for(int i = 0;i < 2*v;i++){
        for(int j = 0;j < e;j++){
            EDGE tmp = arr[j];
            if(d[tmp.from] != INF && d[tmp.to] > d[tmp.from] + tmp.cost){
                d[tmp.to] = d[tmp.from] + tmp.cost;
                if(i >= v-1 && tmp.to == t){
                    return true;
                }

            }
        }
    }
    return false;
}


int main(){

    ll v,e,r,t;/*v:頂点の個数、e:辺の個数、r:始点となる頂点の番号*/
    cin >> v >> e;
    vector<EDGE> arr(ARRAY_MAX);/*辺の情報を格納*/
    vector<ll> d(ARRAY_MAX,0);/*負の閉路があるかの判定、0で初期化*/
   
    REP(i,e){
        cin >> arr[i].from >> arr[i].to >> arr[i].cost;
        arr[i].from--;
        arr[i].to--;/*配列添え字に合わせる*/
        arr[i].cost = -arr[i].cost;
    }

   
    bool exist_negative_cycle = shortest_path(v,e,0,v-1,arr,d);

    if(exist_negative_cycle){
        /*負の閉路が存在する場合*/
        cout << "inf" << endl;
    }else{
        cout << -d[v-1] << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define modulo 1000000007
typedef long long int ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

int main(int argc, char const *argv[])
{
	int n; cin >> n;
	vector<int> a(n);
	int sum(0);
	rep(i,0,n){
		cin >> a[i];
		sum += a[i];
	}

	vector<int> x(n);
	int res(sum);
	for(int i=0; i<n; i++){
		if(i%2==1) res -= 2*a[i];
	}
	x[0] = res;

	for(int i=0; i<n-1; i++){ 
		x[i+1] = 2*a[i] - x[i];
	}

	rep(i,0,n) cout << x[i] << endl;

	return 0;
}


Measured memory_bytes: 2048
#ifndef DEBUG
#    pragma GCC optimize("O3,no-stack-protector")
#    pragma GCC optimize("unroll-loops")

#    if __cplusplus < 201703L
#        pragma GCC target("avx")
#    else
#        pragma GCC target("avx2")
#    endif

#endif

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define dump(x) cout << x << endl
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REP(i, n) for (int i = 0, i##_len = (n); i <= i##_len; ++i)
#define rep3(i, l, r) for (int i = l, i##_len = (r); i < i##_len; ++i)
#define REP3(i, l, r) for (int i = l, i##_len = (r); i <= i##_len; ++i)
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
typedef int64_t Int;
typedef long double Ld;

using namespace std;
template <class T>
using Graph = vector<vector<T>>;

const Ld pi = M_PI;
const Int MOD = 1000000007;
const Int INF = 1LL << 62;

Int Floor(Int a, Int b) {
    return (a - (a % b)) / b;
}

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

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

template <typename T>
inline T Gcd(T a, T b) {
    T c;
    while (b) {
        c = b;
        b = a % b;
        a = c;
    }
    return a;
}

Int Lcm(Int a, Int b) {
    if (a < b) {
        swap(a, b);
    }

    return a / Gcd(a, b) * b;
}

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

    int n;
    string s, t;
    cin >> n >> s >> t;

    string ans = s;
    if (s != t) {
        for (int i = 0; i < n; i++) {
            int ro = n - i;
            bool flag = true;
            for (int j = 0; j < ro; j++) {
                if (t[j] != s[i + j]) {
                    flag = false;
                    break;
                }
            }

            if (flag) {
                for (int j = n - i; j < n; j++) {
                    ans += t[j];
                }
            }
        }

        if (ans == s && ans != t) {
            ans += t;
        }
    }

    cout << ans.size() << endl;

    return 0;
}


Measured memory_bytes: 3628
#include "bits/stdc++.h"
using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
ld EPS = 1e-12;
int INF = numeric_limits<int>::max() / 2;
int MOD = 1e9 + 7;
#define rep(i,n) for(int i = 0; i < n; i++)
#define all(obj) (obj).begin(), (obj).end()
#define debug(x) cerr << #x << ": " << x << '\n'

int n, a, b;
vl v;


long long combination(int n, int r)
{
    if(n < r)
        return 0;
    if(n-r < r)
        r = n-r;
    long long ret = 1;
    for(int i=0; i<r; i++){
        ret *= (n--);
        ret /= i+1;
    }
    return ret;
}
 
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,a,b;
    cin >> n >> a >> b;
    v.resize(n);
    rep(i,n) cin >> v[i];

    sort(v.begin(), v.end(), greater<ll>());

    cout.setf(ios_base::fixed, ios_base::floatfield);
    cout << setprecision(10);

    ll sum = 0;
    rep(i,a) sum += v[i];
    cout << sum / (double)a << endl;

    int num_max = 0;
    int num_min = 0;
    rep(i,n){
        if(v[i] == v[a-1]){
            num_max++;
            if(i < a) num_min++;
        }
    }

    ll ret = 0;

    if(v[0] != v[a-1]){
        ret += combination(num_max, num_min);
    }else{
        for(int i = a; i <= b; i++){
            ret += combination(num_max, i);
        }
    }

    cout << ret << endl;
    return 0;
    
}

Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順

const int MAX = 2010000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}



int main() {
    COMinit();
    int X,Y; cin >> X >> Y;
    if ((X + Y) % 3 != 0) {
        cout << 0 << endl;
        return 0;
    }
    int n, m; 
    m = (2 * X - Y) / 3;
    n = X - 2 * m;
    if (n < 0 || m < 0) {
        cout << 0 << endl;
        return 0;
    }

    cout << COM(n + m, n) << endl;
}

Measured memory_bytes: 50704
#include<iostream>
#include<cstdio>

using namespace std;

const int N(3009);

int n, m;
double ans;
double p[N], f[N][N];

int main()
{
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		cin>>p[i];
	}
	f[0][0] = 1;
	for (int i=1;i<=n;i++)
	{
		f[i][0] = f[i - 1][0] * (1 - p[i]);
	}
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=i;j++)
		{
			f[i][j] = f[i - 1][j - 1] * p[i] + f[i - 1][j] * (1 - p[i]);
		}
	}
	for (int i=n/2+1;i<=n;i++)
	{
		ans += f[n][i];
	}
	printf("%.9lf\n", ans);
}

Measured memory_bytes: 69120
H, W, K = map(int, input().split())
c = [list(input()) for i in range(H)]

ans = 0
for i in range(2 ** H):
  for j in range(2 ** W):
    B = 0
    for k in range(H):
      for l in range(W):
        if (i >> k) & 1 == 0 and (j >> l) & 1 == 0 and c[k][l] == '#':
          B += 1
              
    if B == K:
      ans += 1
print(ans)

Measured memory_bytes: 9108
#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,k;
    cin >> n >> k;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    ll sum = 0;
    rep(i,n) sum += a[i];
    set<ll> c;
    for (int i = 1; i*i < sum; i++){
        if (sum%i==0){
            c.insert(i);
            c.insert(sum/i);
        }
    }
    ll ans = 1;
    for (ll x: c){
        ll now = 1e18;
        vector<ll> r(n);
        rep(i,n) r[i]=a[i]%x;
        sort(r.begin(),r.end());
        ll ms = 0;
        ll mm = 0;
        rep(i,n) ms += x-r[i];
        rep(i,n){
            ms -= x-r[i];
            mm += r[i];
            now = min(now,max(ms,mm));


        }
        if (now <= k){
            ans = max(ans,x);
        }


    }
    cout << ans << endl;
}

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

int main(){
    int N,M;
    cin>>N>>M;
    int X[100001];
    for(int i=0;i<N;i++){
        cin>>X[i];
    }
    if(M==1){
        cout<<N/2<<endl;
    }else{
        int dat[100001]={};
        int pai[100001]={};
        for(int i=0;i<N;i++){
            dat[X[i]]++;
        }
        int real_dat[100001]={};
        for(int i=0;i<=100000;i++){
            int z=i%M;
            real_dat[z] += dat[i];
            if(dat[i]>=2){
                pai[z]+=dat[i]/2;
            }
        }
        /*
         for(int i=0;i<M;i++){
         cout<<i<<' '<<real_dat[i]<<' '<<pai[i]<<endl;
         }*/
        int res=0;
        for(int i=0;i<=M/2;i++){
            int tmp;
            if(i==0){
                tmp=real_dat[i]/2;
                real_dat[i] -= 2*tmp;
                res += tmp;
            }else if(M%2==0 && i==M/2){
                tmp=real_dat[i]/2;
                real_dat[i] -= 2*tmp;
                res += tmp;
            }else{
                tmp = min(real_dat[i] , real_dat[M-i]);
                res += tmp;
                real_dat[i] -= tmp;
                real_dat[M-i] -= tmp;
            }
            //cout<<i<<' '<<tmp<<endl;
        }
        for(int i=1;i<M;i++){
            if(pai[i]!=0){
                res += min(real_dat[i]/2,pai[i]);
            }
        }
        cout<<res<<endl;
    }
    
    
    
    return 0;
}


Measured memory_bytes: 1792
#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>;

bool is_prime(int num) {
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false;

    double sqrt_num = sqrt(num);
    for (int i = 3; i <= sqrt_num; i += 2) {
        if (num % i == 0)
            return false;
    }

    return true;
}

int main() {
    int X; cin >> X;
    while (true) {
        if (is_prime(X)) {
            cout << X << endl;
            return 0;
        }
        X++;
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <string>

using namespace std;

int main() {
  int N,K,sum=0;
  cin >> N >> K;

  for(int i=0; i< N;i++){
    int x;
    cin >> x;
    if(x < K -x){
      sum += x;
    }else{
      sum += K -x;
    }
  }
  cout << sum*2 << endl;
}


Measured memory_bytes: 256
import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.conv;

void main() {
	auto s = readln.chomp;
	string res;
	foreach(i; s) {
		switch(i) {
			case '0', '1':
				res ~= i;
				break;
			case 'B':
				if(res.length != 0) res.popBack();
				break;
			default: break;
		}
	}
	res.writeln;
}

// ===================================

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (isBasicType!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

int ri() {
	return readAs!int;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <numeric>

using namespace std;

long gcd(long m, long n){

	while (m % n != 0)
	{
		long temp = n;
		n = m % n;
		m = temp;
	}
	return n;
}


int main(){
 long a,b,c,d;
  cin >> a >> b >> c >> d;
  long resb,resa;
  long cd;
  
 
  cd=(c*d)/gcd(c,d);
  
  resa=(a-1)-(a-1)/c-(a-1)/d+(a-1)/cd;
  resb=b-b/c-b/d+b/cd;  
  
 
  cout << resb-resa << endl;
}

Measured memory_bytes: 256
def a(N):
    if N == 0:
        return 1
    else:
        return a(N-1)*2 + 3


def p(N):
    if N == 0:
        return 1
    else:
        return p(N-1)*2 + 1


def judge(N, X, an, pn, tp):
    # print('---------')
    sn = an
    sl = int((an - 3) / 2)
    pl = int((pn - 1) / 2)
    # print('TIme' + str(N))
    # print('X'+str(X))
    # print('sl'+str(sl))
    # print('sn' + str(sn))
    # print('tp' + str(tp))
    if X == 1:
        # print('Step1')
        if N == 0:
            return tp + 1
        else:
            return tp + 0
    elif (X > 1) & (X < sl+1):
        # print('Step2')
        return judge(N-1, X-1, sl, pl, tp)
    elif (X == sl + 1) | (X == sl + 2):
        # print('Step3')
        if X == sl + 1:
            tp = pl + tp
            return tp
        else:
            tp = pl + 1 + tp
            return tp
    elif (X > sl + 2) & (X < sn):
        # print('Step4')
        tp = pl + 1 + tp
        return judge(N-1, X-sl-2, sl, pl, tp)
    elif X == sn:
        # print('Step5')
        return tp + pn


N, X = map(int, input().split())
an = a(N)
pn = p(N)
tp = 0
result = judge(N, X, an, pn, tp)
# print(an)
# print(pn)
print(result)

Measured memory_bytes: 3064
#include <iostream>
#include <iomanip> // << fixed << precision(10)
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
using namespace std;

#define FOR(i,s,t) for(int i=s;i<t;i++)
#define REP(i,n) FOR(i,0,n)
#define PRINT(s) cout << s << "\n"
#define SORT(A) sort(A.begin(), A.end())
#define EACHPRINT(A, T) for_each(begin(A), end(A), [&](T i){ cout << i << " "; });cout << "\n"

typedef long lint;
typedef pair<lint, lint> P;

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

    lint res = 0;
    lint W_count = 0;
   
    REP(i, s.length()) {
      if(s[i] == 'B') {
        //        B_count++;
      }
      if (s[i] == 'W'){
        res += (i-W_count);
        W_count++;
        
      }
    }

    cout << res << "\n";

    return 0;
}


Measured memory_bytes: 720
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int INF = 1e9;
int main() {
	string S;
	ll K;
	cin >> S >> K;
	int x = min((ll)S.size(), K);
	for (int i = 0; i < x; ++i) {
		if (S[i] != '1') {
			cout << S[i] << endl;
			return 0;
		}
	}
	cout << 1 << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <map>
#include<unordered_map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include<bitset>
#include<deque>
#include<string>
#include<list>
#include<iterator>
#include<sstream>
#include <algorithm>
#include <numeric>
#include <math.h>

#define user spaesk
#define lli long long int
#define ld long double
#define ff first
#define ss second
#define lower(a) transform(a.begin(),a.end(),a.begin(),::tolower);

using namespace std;

const int N = 3e5 + 500;
const long long mod = 1e9 + 7;
const long long cmod = 998244353 ;
const long long inf = 1LL << 61;
const int M = 1e6 + 500;
const lli ths = 1LL << 40;
const int NN = 5e3 + 6;

void solve()
{

    lli n;
    cin>>n;
    string s;
    set<string > st;
    for(int i = 0; i < n; i ++) {
        cin>>s;
        st.insert(s);
    }
    cout<<st.size();
    cout<<"\n";
    return ;
}

/*
*/

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

    int t = 1;
//    cin>>t;
    while(t --)
    {
        solve();
    }
    return 0;
}


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

int main() {
  int a, b, x;
  cin >> a >> b;
  for(int i=1; i<b-a; i++){
    x=x+i;
  }
  cout << x-a << endl;
}

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

#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) ((int)(x).size())
#define pb push_back
#define fst first
#define snd second
#define PI (acos(-1))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))

#define MAXN 1123456
#define MOD 1000000007

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vii;
typedef vector<vi> vvi;

const int MAX_PR = 5'000'000;
bitset<MAX_PR> isprime;
vi eratosthenes_sieve(int lim) {
  isprime.set(); isprime[0] = isprime[1] = 0;
  for (int i = 4; i < lim; i += 2) isprime[i] = 0;
  for (int i = 3; i*i < lim; i += 2) if (isprime[i])
    for (int j = i*i; j < lim; j += i*2) isprime[j] = 0;
  vi pr;
  rep(i,2,lim) if (isprime[i]) pr.push_back(i);
  return pr;
}

const ll mod = 1000000007; // faster if const

ll modpow(ll b, ll e) {
  ll ans = 1;
  for (; e; b = b * b % mod, e /= 2)
    if (e & 1) ans = ans * b % mod;
  return ans;
}


ll inv(ll n) {return modpow(n, mod-2);}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);

  int n;
  cin >> n;
  vi a(n);
  rep(i,0,n) cin >> a[i];

  vi pr = eratosthenes_sieve(1123);
  map<int, int> pw;
 // cerr << sz(pr) << endl;

  trav(k, a) {
    ll K = k;
    trav(p, pr) {
      ll P = p;
      int po = 1;
      while (P <= k) {
        if (k%P == 0) {
          pw[p]=max(pw[p], po);
          K /= p;
        }
        P *= p;
        ++po;
      }
    }
    if (K > 1) pw[K] = 1;
  }

  ll lcm = 1;
  trav(pa, pw) {
    lcm = lcm * modpow(pa.fst, pa.snd);
//    cerr << pa.fst << ' ' << pa.snd  << endl;;
    lcm %= mod;
  }


  ll ans = 0;
  trav(k, a) {
    ans += (lcm * inv(k))%mod;
    ans %= mod;
  }

  
  cout << ans << endl;

}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
#define INF 1e18

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef vector < pair<int, int> > vii;
typedef long double ld;
typedef tree<pair<int,int>, null_type, less<pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

ll sparse_odd[222222][20], sparse_even[222222][20], idx[222222], a[222222];

bool cmp(ii a, ii b){
	ll x = INF;
	ll y = INF;
	ll l = a.fi;
	ll r = a.se;
	if(l%2==0){
		for(int i = 19; i >= 0; i--){
			if(l+(1<<i)-1<r){
				x=min(x,sparse_even[l][i]);
				l+=(1<<i);
			}
		}
	}
	else{
		for(int i = 19; i >= 0; i--){
			if(l+(1<<i)-1<r){
				x=min(x,sparse_odd[l][i]);
				l+=(1<<i);
			}
		}
	}
	l = b.fi;
	r = b.se;
	if(l%2==0){
		for(int i = 19; i >= 0; i--){
			if(l+(1<<i)-1<r){
				y=min(y,sparse_even[l][i]);
				l+=(1<<i);
			}
		}
	}
	else{
		for(int i = 19; i >= 0; i--){
			if(l+(1<<i)-1<r){
				y=min(y,sparse_odd[l][i]);
				l+=(1<<i);
			}
		}
	}
	return x>y;
}

priority_queue <ii, vii, function<bool(ii,ii)> > solve(cmp);
vector<ii> ans;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n;
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		idx[a[i]]=i;
		if(i%2){
			sparse_odd[i][0]=a[i];
			sparse_even[i][0]=INF;
		}
		else{
			sparse_odd[i][0]=INF;
			sparse_even[i][0]=a[i];
		}
	}
	for(int j = 1; j < 20; j++){
		for(int i = 0; i < n; i++){
			if(i+(1<<j)-1<n){
				sparse_even[i][j]=min(sparse_even[i][j-1],sparse_even[i+(1<<(j-1))][j-1]);
				sparse_odd[i][j]=min(sparse_odd[i][j-1],sparse_odd[i+(1<<(j-1))][j-1]);
			}
		}
	}
	solve.push(mp(0,n));
	while(!solve.empty()){
		ll l, r, l1;
		ll x=INF;
		l = solve.top().fi;
		r = solve.top().se;
		solve.pop();
		if(l<r){
			if(l%2==0){
			l1=l;
			for(int i = 19; i >= 0; i--){
				if(l+(1<<i)-1<r){
					x=min(x,sparse_even[l][i]);
					l+=(1<<i);
				}
			}
			ll y=INF;
			l=idx[x]+1;
			for(int i = 19; i >= 0; i--){
				if(l+(1<<i)-1<r){
					y=min(y,sparse_odd[l][i]);
					l+=(1<<i);
				}
			}
			ans.pb(mp(x,y));
			solve.push(mp(l1,idx[x]));
			solve.push(mp(idx[x]+1,idx[y]));
			solve.push(mp(idx[y]+1,r));
			}
			else{
				l1=l;
				for(int i = 19; i >= 0; i--){
					if(l+(1<<i)-1<r){
						x=min(x,sparse_odd[l][i]);
						l+=(1<<i);
					}
				}
				ll y=INF;
				l=idx[x]+1;
				for(int i = 19; i >= 0; i--){
					if(l+(1<<i)-1<r){
						y=min(y,sparse_even[l][i]);
						l+=(1<<i);
					}
				}
				ans.pb(mp(x,y));
				solve.push(mp(l1,idx[x]));
				solve.push(mp(idx[x]+1,idx[y]));
				solve.push(mp(idx[y]+1,r));
			}
		}
	}
	for(int i = 0; i < ans.size(); i++){
		cout << ans[i].fi << ' ' << ans[i].se << ' ';
	}
	return 0;
}


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

using namespace std;

#define N 1
int n, a, b;
string x;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> a >> b;
    cin >> x;
    n = a + b + 1;
    bool ok = true;
    for (int i = 0; i < a; i++)
        if (x[i] < '0' || x[i] > '9')
            ok = false;
    ok = ok && x[a] == '-';
    for (int i = 0; i < b; i++)
        if (x[i + a + 1] < '0' || x[i + a + 1] > '9')
            ok = false;
    cout << (ok ? "Yes" : "No") << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> VL;
typedef vector<pair<ll, ll>> VPI;
typedef pair<ll, ll> PLL;
typedef map<ll, ll> MLL;
#define EPS 1e-9
#define pb push_back
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, k;
    cin >> n >> k;
    VL h(n + 1);
    FOR(i, 1, n + 1)
    {
        cin >> h[i];
    }
    VL dp(n + 1, 0);
    dp[1] = 0;
    FOR(i, 2, k + 1)
    {
        int minimum = INT_MAX;
        FOR(j, 1, i)
        {
            if (dp[i - j] + abs(h[i] - h[i - j]) < minimum)
            {
                minimum = dp[i - j] + abs(h[i] - h[i - j]);
            }
            dp[i] = minimum;
        }
    }
    FOR(i, k + 1, n + 1)
    {
        int minimum = INT_MAX;
        FOR(j, 1, k + 1)
        {
            if (dp[i - j] + abs(h[i] - h[i - j]) < minimum)
            {
                minimum = dp[i - j] + abs(h[i] - h[i - j]);
            }
            dp[i] = minimum;
        }
    }
    cout << dp[n] << "\n";
    return 0;
}


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

int main(){
  string s, t;
  cin >> s >> 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: 3636
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define PI  3.14159265358979323846
#define lp(i,n) for(int i = 0; i <n;i++)
#define rlp(i,n) for(int i = int(n);i >= 0;i--)
#define range1(i,a,b,c) for(int i = int(a);i <= int(b);i+=int(c))
#define range(i,a,b) for(int i = int(a);i <= int(b);i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define sz(v) ((int)((v).size()))
#define sfi1(v) scanf("%d",&v)
#define sfi2(v1, v2) scanf("%d %d",&v1,&v2)
#define sfi3(v1, v2, v3) scanf("%d %d %d",&v1,&v2,&v3)
#define sfll1(v) scanf("%I64d",&v);
#define sfll2(v1, v2) scanf("%I64d %I64d",&v1,&v2)
#define sfll3(v1, v2, v3) scanf("%I64d %I64d %I64d",&v1,&v2,&v3)
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<pair<int, int> > vii;
typedef pair<int, int> pii;
template<class T> using ordered_set=tree<T,
null_type,
less<T>,
rb_tree_tag,
tree_order_statistics_node_update>;
const ll MOD = 1e9 + 7;
const int OO = (int)1e6;
const int N = (int)1e7;
int dx[] = {0,0,-1,1};
int dy[] = {1,-1,0,0};
void init(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
int a[N];
void _run(){
   int n;
   scanf("%d",&n);
   ll sum =0;
   lp(i,n){
       scanf("%d",&a[i]);
       sum+=a[i];
   }
   ll total = 0;
   lp(i,n){
        sum-=a[i];
       total=total%MOD+(sum%MOD*a[i]%MOD)%MOD;
      
   }
   cout<<total<<endl;
}
int main() {
	#   ifdef LOCAL_PROJECT
        freopen("in.txt", "r", stdin);
    #   endif
    int t=1;
    // scanf("%d",&t);
    while(t--)_run();
    
    return 0;
}

Measured memory_bytes: 4468
//headers
#include <bits/stdc++.h>
#include <chrono>
#define ll long long
using namespace std;
using namespace chrono;
void solve()
{
    double d, t, s;
    cin >> d >> t >> s;
    if(d/s <= t)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    

}

//driver
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//#ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//#endif
    auto t1 = high_resolution_clock::now();
    ll test = 1;
    // cin >> test;
    for (ll i = 0; i < test; i++)
    {
        // cout << "Case #" << (i + 1) << ": ";
        solve();
    }
    auto t2 = high_resolution_clock::now();
    auto duration = duration_cast<milliseconds>(t2 - t1).count();
    // cout << duration << endl;
    return 0;
}

Measured memory_bytes: 3736