akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define dump(...) cout<<"# "<<#__VA_ARGS__<<'='<<(__VA_ARGS__)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

using uint=unsigned;
using ll=long long;
using ull=unsigned long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using vd=vector<double>;
using vvd=vector<vd>;
using vs=vector<string>;

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

template<typename Tuple>
void print_tuple(ostream&,const Tuple&){}
template<typename Car,typename... Cdr,typename Tuple>
void print_tuple(ostream& os,const Tuple& t){
	print_tuple<Cdr...>(os,t);
	os<<(sizeof...(Cdr)?",":"")<<get<sizeof...(Cdr)>(t);
}
template<typename... Args>
ostream& operator<<(ostream& os,const tuple<Args...>& t){
	print_tuple<Args...>(os<<'(',t);
	return os<<')';
}

template<typename Ch,typename Tr,typename C>
basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>& os,const C& c){
	os<<'[';
	for(auto i=begin(c);i!=end(c);++i)
		os<<(i==begin(c)?"":" ")<<*i;
	return os<<']';
}

constexpr int INF=1e9;
constexpr int MOD=1e9+7;
constexpr double EPS=1e-9;

int main()
{
	for(ll n,a,b,c,d;cin>>n>>a>>b>>c>>d;){
		bool ok=false;
		rep(i,n){
			ll mn=-d*i+c*(n-1-i);
			ll mx=-c*i+d*(n-1-i);
			ok|=mn<=b-a&&b-a<=mx;
		}
		cout<<(ok?"YES":"NO")<<endl;
	}
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <unordered_map>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>
#include <assert.h>
#include <unordered_map>
#include <fstream>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef pair<ll,ll> P;
typedef pair<int,int> pii;
typedef vector<P> vpl;
typedef tuple<ll,ll,ll> tapu;
#define rep(i,n) for(int i=0; i<(n); i++)
#define REP(i,a,b) for(int i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int MAX = 510000;
ll dy[8] = {1,-1,0,0,1,-1,1,-1};
ll dx[8] = {0,0,1,-1,1,-1,-1,1};
const double pi = acos(-1);
const double eps = 1e-7;
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){
	if(a>b){
		a = b; return true;
	}
	else return false;
}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){
	if(a<b){
		a = b; return true;
	}
	else return false;
}
template<typename T> inline void print(T &a){
    rep(i,a.size()) cout << a[i] << " ";
    cout << "\n";
}
template<typename T1,typename T2> inline void print2(T1 a, T2 b){cout << a << " " << b << "\n";}
template<typename T1,typename T2,typename T3> inline void print3(T1 a, T2 b, T3 c){
	cout << a << " " << b << " " << c << "\n";
}
const int mod = 1e9 + 7;
//const int mod = 998244353;

vector<ll> fac(MAX), finv(MAX), inv(MAX);

void comInit(){
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for(ll 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;
	}
}


ll com(ll n, ll 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(){
	ll h,w,n; cin >> h >> w >> n;
	vpl v(n);
	rep(i,n) cin >> v[i].first >> v[i].second;
	comInit();
	sort(all(v));
	v.emplace_back(h,w);
	vl dp(n+1,0);
	rep(i,n+1){
		dp[i] = com(v[i].first+v[i].second-2,v[i].first-1);
		rep(j,i){
			ll H = v[i].first - v[j].first;
			ll W = v[i].second - v[j].second;
			if(W < 0) continue;
			dp[i] -= dp[j] * com(H+W,H) % mod;
			if(dp[i] < 0) dp[i] += mod;
		}
	}
	cout << dp[n] << "\n";
}

Measured memory_bytes: 15440
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>

using namespace std;

long solve(const string& x) {
  int slen = 0;
  int tlen = 0;
  for (auto c : x) {
    if (c == 'S') {
      ++slen;
    } else if (slen > 0) {
      --slen;
    } else {
      ++tlen;
    }
  }
  return slen + tlen;
}

int main() {
  string x;
  cin >> x;
  
  cout << solve(x) << endl;

  return 0;
}

Measured memory_bytes: 640
def d_2017LikeNumber(Q, I):  # Q:クエリの数、I:探索区間の左端と右端
    def prime_list(M):
        # 0以上M以下の素数のリスト
        s = [True] * (M + 1)  # i番目の要素はiが素数ならTrue、非素数ならFalse
        s[0] = s[1] = False
        for x in range(2, int(M**0.5) + 1):
            if s[x]:
                for i in range(x + x, len(s), x):
                    # 素数xの倍数は素数ではない
                    s[i] = False
        return s

    def calc_like2017(M, p):
        # i番目の要素が、1以上i以下の"2017に似た数"の個数となるようなリスト
        # 0番目は0と定義する
        # M以下の素数のリストpを予め作っておく必要がある
        c = [0] * (M + 1)
        for i in range(3, M + 1, 2):  # 0,1,2は定義上2017に似た数にならない
            if p[i] and p[(i + 1) // 2]:
                c[i] += 1
        for i in range(3, M + 1):
            c[i] += c[i - 1]
        return c

    c = calc_like2017(10**5, prime_list(10**5))
    ans = ''
    for query in I:
        l, r = query[0], query[1]
        ans += '{}\n'.format(c[r] - c[l - 1])
    return ans[:-1]

Q = int(input())
I = [[int(i) for i in input().split()] for j in range(Q)]
print(d_2017LikeNumber(Q, I))

Measured memory_bytes: 24944
#include <algorithm>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <queue>
#include <stack>
#include <utility>
#include <vector>
using std::cin;
using std::cout;
using std::endl;

const int INF = 1000;

int solve(std::string s, char c) {
    int res = 0;
    int tmp = 0;
    for (auto x : s) {
        if (x == c) {
            if (tmp > res)
                res = tmp;
            tmp = 0;
        } else {
            tmp++;
        }
    }
    if (tmp > res)
        res = tmp;
    return res;
}

int main(void) {
    cout << std::fixed << std::setprecision(10);
    cin.tie(0);
    std::ios::sync_with_stdio(false);

    int res = INF;
    std::string s;
    cin >> s;
    for (char c = 'a'; c <= 'z'; c++) {
        int tmp = solve(s, c);
        if (res > tmp)
            res = tmp;
    }
    cout << res;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>	
#include<cmath>
#include<map>
#include<vector>
#include<math.h>
#define int long long
using namespace std;
signed main() {
	int n, ans = 0; string s; cin >> n;
	for (int h = 0; h < n; h++) {
		cin >> s;
		if (s == "E869120") { ans++; }
	}
	cout << ans << endl;
}


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

typedef long long ll;

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define ANS(n) cout << (n) << endl

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FORR(i,a,b) for(int i=(a);i>=(b);i--)

#define ALL(obj) (obj).begin(),(obj).end()

#define pii pair<int,int>

#define pb(a) push_back(a)
#define mp make_pair

int main()
{
	int h,w;
	cin >> h >> w;
	int c[10][10];
	FOR(i,0,10)FOR(j,0,10)cin >> c[i][j];
	FOR(k,0,10)FOR(i,0,10)FOR(j,0,10){
		c[i][j] = min(c[i][j], c[i][k] + c[k][j]);
	}
	int ans = 0;
	FOR(i,0,h)FOR(j,0,w){
		int a;
		cin >> a;
		if(a == -1)continue;
		ans += c[a][1];
	}
	ANS(ans);
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define EPS (1e-10)
#define EQ(a,b) (abs((a)-(b))<EPS)

const double PI=4*atan(1.0);

int main(){

    double r;
    while(cin>>r&&!EQ(r,0)){
        bool f=false;
        for(int i = 1; ; i++){
            int d[2];
            d[0]=ceil(i*PI+EPS);
            d[1]=floor(i*PI+EPS);
            for(int k = 0; k < 2; k++){
                int j=d[k];
                if(EQ(abs(((double)j/i)-PI),r)||abs(((double)j/i)-PI)<r){
                    cout<<j<<"/"<<i<<endl;
                    f=true;
                    break;
                }
            }
            if(f)
                break;
        }
    }
    return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<functional>
#include<queue>
#include <iomanip>
#include<map>
#include<limits>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<utility>
#include<complex>
#include<cstdlib>
#include<set>
#include<cctype>

#define DBG cerr << '!' << endl;
#define REP(i,n) for(int (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(int (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(int (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int i = 0;i < (n);i++)cerr << v[i] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()

using namespace std;

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;
typedef vector<string> sv;

int num[4];
int ans;

int main()
{
	ll n,w,w1,v1;cin>>n>>w>>w1>>v1;
	
	vector<ll> v[4];
	
	v[0].PB(v1);
	
	REP(i,n-1)
	{
		int x,y;cin>>x>>y;
		v[x-w1].PB(y);
	}
	
	REP(i,4)
	{
		sort(ALL(v[i]),greater<ll>());
		num[i] = v[i].size();
		rep(j,1,v[i].size())
		{
			v[i][j] += v[i][j-1];
		}
	}
	
	//SHOW1d(num,4);
	 
	int par[4] = {};
	ll ans = 0;
	
	while(1)
	{
		//SHOW1d(par,4);
		
		bool flag = true;
		
		ll tmp = 0;
		REP(i,4)
		{
			if(par[i] > 0)
			{
				tmp += v[i][par[i]-1];
			}
		}
		
		if(w >= par[0]*w1 + par[1]*(w1+1) + par[2]*(w1+2) + par[3]*(w1+3))
			ans = max(ans,tmp);

		REP(i,4)
		{
			if(par[i] != num[i])flag = false;
		}
		if(flag)break;

		
		par[0]++;
		
		REP(i,3)
		{
			if(par[i] > num[i])
			{
				par[i] = 0;par[i+1]++;
			}
		}
	}
	
	cout << ans << endl;
		
	
	return 0;
}

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

using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
typedef long long ll;

int main(){
  int x,a,b;
  cin >> x >> a >> b;
  if(abs(x-a)<abs(x-b))cout << "A" << endl;
  else cout << "B" << endl;
}


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

using namespace std;

int main()
{
    string S, T;

    cin >> S >> T;

    int c = 0;
    for ( int i = 0; i < S.length(); i ++) {
        if ( S[i] != T[i] ) c ++;
    }

    cout << c << endl;

    return 0;
}

Measured memory_bytes: 3856
a, b, c, x, y = map(int, input().split())
total = 0

if a > 2*c:
    total += 2 * c * x
    y -= x
    x = 0

if b > 2*c:
    total += 2 * c * y
    x -= y
    y = 0

if a + b > 2*c:
    if x < 0: x = 0
    if y < 0: y = 0
    z = min(x, y)
    x = max(0, x-z)
    y = max(0, y-z)
    total += x*a + y*b + z*c*2
else:
    total += x*a + y*b

print(total)


Measured memory_bytes: 3064
N, M = map(int, input().split())
W, V = [], []
for n in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
X = sum(V)
# f[n][x] = n番目までの品物でx以上の価値に必要な最小の重さ
f = [[10**9 for x in range(X + 1)] for n in range(N + 1)]
f[0][0] = 0
for n in range(1, N + 1):
    for x in range(X + 1):
        if x >= V[n - 1]:
            f[n][x] = min(f[n - 1][x], f[n - 1][x - V[n - 1]] + W[n - 1])
        else:
            f[n][x] = f[n - 1][x]
ans = X
while f[N][ans] > M:
    ans = ans - 1
print(ans)


Measured memory_bytes: 173448
#include<stdio.h>
#include<string.h>
int main(){
    while(1){
        int n,m,a,line[100][1000];
        scanf("%d %d %d",&n,&m,&a);
        memset(line,0,sizeof(line));
        if(n==0&&m==0&&a==0) return 0;
        for(int i=0;i<m;i++){
            int h,p,q;
            scanf("%d %d %d",&h,&p,&q);
            line[p-1][h-1]=q-p;
            line[q-1][h-1]=p-q;
        }
        for(int i=999;i>=0;i--){
            a+=line[a-1][i];
        }
        printf("%d\n",a);
    }
}

Measured memory_bytes: 1424
# https://atcoder.jp/contests/abc092/tasks/abc092_b


N = gets.to_i
D, X = gets.split.map(&:to_i)
As = Array.new(N) { gets.to_i }

ans = X + As.reduce(0) { |memo, a| memo + (D - 1) / a + 1 }

puts ans


Measured memory_bytes: 1788
def dice(m, n):
    for i in range(0, n-2):
        if (m[i][0] == m[i][1]) and (m[i + 1][0] == m[i + 1][1]) and (m[i + 2][0] == m[i + 2][1]): 
            return 'Yes'
    return 'No'

N = int(input())
mylist = []
for i in range(0, N):
    num = list(map(int, input().split(' ')))
    mylist.append(num)

print(dice(mylist, N))

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

int main() {
  int n;
  cin>>n;
  for(int i=1; i<10; i++){
    for(int j=1; j<10; j++){
      if(i*j == n) {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define codefor int test;scanf("%d",&test);while(test--)
#define yn(ans) cout<<(ans?"Yes":"No")<<endl
#define YN(ans) cout<<(ans?"YES":"NO")<<endl
#define umap unordered_map
#define uset unordered_set
using namespace std;
using ll = long long;
//入力系
void scan(int& a){scanf("%d",&a);}
void scan(long long& a){scanf("%lld",&a);}
template<class T> void scan(T& a){cin>>a;}
template<class T> void scan(vector<T>& vec){for(auto&& it:vec)scan(it);}
void in(){}
template <class Head, class... Tail> void in(Head& head, Tail&... tail){scan(head);in(tail...);}
//出力系
void print(const int& a){printf("%d",a);}
void print(const long long& a){printf("%lld",a);}
void print(const double& a){printf("%.15lf",a);}
template<class T> void print(const T& a){cout<<a;}
template<class T> void print(const vector<T>& vec){if(vec.empty())return;print(vec[0]);for(auto it=vec.begin();++it!= vec.end();){putchar(' ');print(*it);}}
void out(){putchar('\n');}
template<class T> void out(const T& t){print(t);putchar('\n');}
template <class Head, class... Tail> void out(const Head& head,const Tail&... tail){print(head);putchar(' ');out(tail...);}
//デバッグ系
template<class T> void dprint(const T& a){cerr<<a;}
template<class T> void dprint(const vector<T>& vec){if(vec.empty())return;cerr<<vec[0];for(auto it=vec.begin();++it!= vec.end();){cerr<<" "<<*it;}}
void debug(){cerr<<endl;}
template<class T> void debug(const T& t){dprint(t);cerr<<endl;}
template <class Head, class... Tail> void debug(const Head& head, const Tail&... tail){dprint(head);cerr<<" ";debug(tail...);}
 
int main(){
    ll n,k;
    in(n,k);
    vector<int> vec(n);
    in(vec);
    for(int i=k;i<n;i++){
        yn(vec[i]>vec[i-k]);
    }
}

Measured memory_bytes: 4024
//! 尺卂乃卂.卂ﾌ乇乇ㄒ
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define mip             map<pair<int,int>,int>
#define mic             map<char,int> 
#define all(v)          v.begin(),v.end()  
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define itr(v)          for(auto it:v)
#define show(arr,n) for(int i=0;i<n;i++) cout<<arr[i]<<" "; cout<<"\n";
#define fi(i,n)         for(int i=0;i<n;i++)
#define fd(i,n)         for(int i=n-1;i>=0;i--)
#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

bool cmp(int a,int b) {return a>b;}
int fast_pow(int b,int p,int m=INT_MAX){
     if(p==0) return 1;
     if(p==1) return b;
    int res=fast_pow(b,p/2,m);  res=(res*res)%m;
    if(p%2==0) return res; else return  (b*res)%m;
}
int mmi(int a,int m){ return fast_pow(a,m-2,m);}

int a[200001],b[200001];

int32_t main()
{
    FIO
    long double n; cin>>n;
   long double c=(log(n)-log(100))/(log(101)-log(100));
   int prev=100;
   int ans=100;
   int i=1;
   double tatti=0;
   for(i=1;i<3780;i++){
       ans=ans+(prev*1.01-prev);
       prev=ans;
       if(ans>=n) break;
   }
   cout<<i<<"\n";
    return 0;
}

Measured memory_bytes: 3800
def resolve():
    N, M = list(map(int, input().split()))
    AB = [list(map(int, input().split())) for i in range(M)]
    d = {}
    for ab in AB:
        if ab[0] not in d:
            d[ab[0]] = [ab[1]]
        else:
            d[ab[0]].append(ab[1])
    if 1 not in d:
        print("IMPOSSIBLE")
        return
    for i in d[1]:
        if i not in d:
            continue
        if N in d[i]:
            print("POSSIBLE")
            return
    print("IMPOSSIBLE")



if '__main__' == __name__:
    resolve()

Measured memory_bytes: 102700
from collections import defaultdict
from collections import deque
from string import ascii_uppercase
import sys, bisect, math, heapq

stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

N = read_int()[0]
A = read_int()

def solve():
    for a in A:
        if a % 2 == 0 and (a % 3 != 0 and a % 5 != 0):
            return "DENIED"
    return "APPROVED"

if __name__ == "__main__":
    print(solve())

Measured memory_bytes: 3760
#include <bits/stdc++.h>
#define Int int64_t

using namespace std;

// [ _UnionFind ]
// Union-Find木 /* union by size */
// 宣言は UnionFind uf(N); のようにする
// find(x) : xの根を求める
// same(x, y) : xとyが同じ集合に属するかどうか
// size(x) : xの属する集合の要素数
// size() : 集合がいくつあるか
// unite(x, y) : xとyの属する集合を併合する
struct UnionFind {
private:
	vector<int> uf;
	size_t sz;

public:
	UnionFind(size_t Size) {
		uf.assign(Size, -1);
		sz = Size;
	}

	int find(int x) { return (uf[x] < 0) ? x : uf[x] = find(uf[x]); }
	bool same(int x, int y) { return find(x) == find(y); }
	int size(int x) { return -uf[find(x)]; }
	int size() { return sz; }

	void unite(int x, int y) {
		x = find(x), y = find(y);
		if (x == y) { return; }
		--sz;

		if (uf[y] < uf[x]) { swap(x, y); }
		uf[x] += uf[y];
		uf[y] = x;
	}
};

int main() {
	int N, M, K;
	cin >> N >> M >> K;
	UnionFind uf(N);
	vector<vector<int>> fr(N), bl(N);
	for (int i = 0; i < M; ++i) {
		int a, b;
		cin >> a >> b;
		--a; --b;
		uf.unite(a, b);
		fr[a].emplace_back(b);
		fr[b].emplace_back(a);
	}
	for (int i = 0; i < K; ++i) {
		int a, b;
		cin >> a >> b;
		--a; --b;
		bl[a].emplace_back(b);
		bl[b].emplace_back(a);
	}

	vector<int> ans(N, 0);
	for (int i = 0; i < N; ++i) {
		ans[i] = uf.size(i) - fr[i].size() - 1;
		for (int v : bl[i]) {
			if (uf.same(i, v)) { --ans[i]; }
		}
	}
	for (int i = 0; i < N; ++i) {
		cout << ans[i] << (i < N - 1 ? " " : "\n");
	}

	return 0;
}


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

int main() {
    int n, m;
    cin >> n >> m;
    vector <long long> a(n + 1, 0);
    rep (i, n) cin >> a[i + 1];
    rep (i, n) a[i + 1] += a[i];
    map <long long, long long> mp;
    for (auto i : a) mp[i % m]++;

    long long ans = 0;
    for (auto m : mp) {
        ans += (m.second * (m.second - 1)) / 2;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4992
INF = 10000000000

n = int(input())
A = [int(x) for x in input().split()]

def merge(A,left,mid,right):
    count = 0
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid] + [INF]
    R = A[mid:right] + [INF]
    #L,Rの中身はAの中身の部分コピーだからいちいちappendするより
    #スライスしてまとめてコピーしたほうが処理が軽い
    #[INF]は番兵みたいなもの
    #[INF]を追加しておくとL,Rを調べつくしての
    #list index out of rangeを回避できる
    i, j = 0, 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    count += right - left
    return count

def mergeSort(A,left,right):
    if left + 1 < right:
        mid = int((left + right) / 2)
        countL = mergeSort(A,left,mid)
        countR = mergeSort(A,mid,right)
        return merge(A,left,mid,right) + countL + countR
    return 0

count = mergeSort(A,0,n)
for i in range(n):
    if i:
        print(" ",end="")
    print(A[i],end="")
print()
print(count)



Measured memory_bytes: 61660
import java.util

object Main {
  def main(args: Array[String]): Unit = {
    val s = new Main()
    s.solve()
    s.out.flush()
  }
}

class Main {
  import java.io._
  import java.util.StringTokenizer

  import scala.collection.mutable
  import scala.util.Sorting
  import math.{abs, max, min}
  import mutable.{ArrayBuffer, ListBuffer}
  import scala.reflect.ClassTag

  val MOD = 1000000007
  val out = new PrintWriter(System.out)

  def solve(): Unit = {
    val N = ni()
    val P = Array.ofDim[Int](N) // 100倍したもの
    REP(N) { i =>
      val p = ns()
      P(i) = p.filter(Character.isDigit).toInt
    }

    val dp = Array.ofDim[Double](2, N + 1)
    dp(0)(0) = 1
    REP(N) { i =>
      val x = i % 2
      util.Arrays.fill(dp(x^1), 0)

      REP(N + 1) { j =>
        if (j > 0) dp(x^1)(j) += dp(x)(j - 1) * P(i) / 100
        dp(x^1)(j) += dp(x)(j) * (100 - P(i)) / 100
      }
    }

    val ans = dp(N%2).zipWithIndex.filter(_._2 > N / 2).map(_._1).sum
    out.println(f"${ans}%.10f")
  }

  class InputReader(val stream: InputStream) {
    private val reader = new BufferedReader(new InputStreamReader(stream), 32768)
    private var tokenizer: StringTokenizer = _

    def next(): String = {
      while (tokenizer == null || !tokenizer.hasMoreTokens)
        tokenizer = new StringTokenizer(reader.readLine)
      tokenizer.nextToken
    }

    def nextInt(): Int = next().toInt
    def nextLong(): Long = next().toLong
    def nextChar(): Char = next().charAt(0)
  }
  val sc = new InputReader(System.in)
  def ni(): Int = sc.nextInt()
  def nl(): Long = sc.nextLong()
  def nc(): Char = sc.nextChar()
  def ns(): String = sc.next()
  def ns(n: Int): Array[Char] = ns().toCharArray
  def na(n: Int, offset: Int = 0): Array[Int] = map(n)(_ => ni() + offset)
  def na2(n: Int, offset: Int = 0): (Array[Int], Array[Int]) = {
    val A1, A2 = Array.ofDim[Int](n)
    REP(n) { i =>
      A1(i) = ni() + offset
      A2(i) = ni() + offset
    }
    (A1, A2)
  }
  def nm(n: Int, m: Int): Array[Array[Int]] = {
    val A = Array.ofDim[Int](n, m)
    REP(n) { i =>
      REP(m) { j =>
        A(i)(j) = ni()
      }
    }
    A
  }
  def nal(n: Int): Array[Long] = map(n)(_ => nl())
  def nm_c(n: Int, m: Int): Array[Array[Char]] = map(n) (_ => ns(m))
  def REP(n: Int, offset: Int = 0)(f: Int => Unit): Unit = {
    var i = offset
    val N = n + offset
    while(i < N) { f(i); i += 1 }
  }
  def REP_r(n: Int, offset: Int = 0)(f: Int => Unit): Unit = {
    var i = n - 1 + offset
    while(i >= offset) { f(i); i -= 1 }
  }

  def map[@specialized A: ClassTag](n: Int, offset: Int = 0)(f: Int => A): Array[A] = {
    val res = Array.ofDim[A](n)
    REP(n)(i => res(i) = f(i + offset))
    res
  }


  def sumL(as: Array[Int]): Long = {
    var s = 0L
    REP(as.length)(i => s += as(i))
    s
  }

  def cumSum(as: Array[Int]) = {
    val cum = Array.ofDim[Long](as.length + 1)
    REP(as.length) { i =>
      cum(i + 1) = cum(i) + as(i)
    }
    cum
  }
}

Measured memory_bytes: 29036
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 0xccccccc;
const ll LINF = 922337203685477580LL;
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}

const int mod = 1000000007;
//const int mod = 998244353;

struct mint {
  int64_t x;
  mint(int64_t x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(int64_t t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  //for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) {return mint(*this) /= a;}
};

istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

//head

using V = vector<mint>;
using M = vector<V>;

M mul(M a, M b) {
  int n = a.size();
  M res(n, V(n));
  rep(i, n) rep(j, n) rep(k, n) res[i][j] += a[i][k] * b[k][j];
  return res;
}
M pow(M &a, ll p) {
  int n = a.size();
  if(!p) {
    M res(n, V(n));
    rep(i, n) res[i][i] = 1;
    return res;
  }
  M res = pow(a, p>>1);
  res = mul(res, res);
  if(p&1) res = mul(res, a);
  return res;
}

int n;
ll k;


int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> k;
  M mat(n, V(n));
  rep(i, n) rep(j, n) cin >> mat[i][j];
  mat = pow(mat, k);

  mint ans;
  rep(i, n) ans += accumulate(all(mat[i]), mint());
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3752
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<P1,ll> P2;
typedef pair<string,string> Ps;
const ll INF=10000000000000000001;
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};
struct pos{
	// 1 変数を入れる;
	ll x,cost;
};
int main() {

	string s,t;
	cin>>s;
	rep(i,s.size())t+='x';
	cout<<t<<endl;
	return 0;
}


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

int cnt;
int r[4005],g[4005],b[4005];

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	string s;
	cin>>n>>s;
	
	for(int i=n-1; i>=0; i--)
	{
		if(s[i]=='R')
			r[i]=r[i+1]+1;
		else
			r[i]=r[i+1];
		if(s[i]=='G')
			g[i]=g[i+1]+1;
		else
			g[i]=g[i+1];
		if(s[i]=='B')
			b[i]=b[i+1]+1;
		else
			b[i]=b[i+1];
	}
	
	for(int i=0; i<n-2; i++)
	{
		for(int j=i+1; j<n-1; j++)
		{
			if(s[j]!=s[i])
			{
				char re;
				if(s[i]!='R' && s[j]!='R')
					re='R';
				else if(s[i]!='G' && s[j]!='G')
					re='G';
				else if(s[i]!='B' && s[j]!='B')
					re='B';
				if(re=='R')
					cnt+=r[j+1];
				else if(re=='G')
					cnt+=g[j+1];
				else if(re=='B')
					cnt+=b[j+1];
				if(2*j-i<n && s[2*j-i]==re)
					cnt--;
			}
		}
	}
	
	cout<<cnt<< endl;
	return 0;
}


Measured memory_bytes: 3660
#include <bits/stdc++.h>
using namespace std;
# define ll long long int
# define ld  long double
# define pb push_back
# define pp pop_back
# define ff first
# define ss second
#define pll pair<ll, ll>
# define mp make_pair
# define ac accumulate
# define mod 1000000007
#define um unordered_map
# define pii pair<ll,ll>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int  main()
{
	ll x,y;
	cin>>x>>y;
	if(x>=13)
	{
		cout<<y;
		return 0;
	}		
	if(x>=6&&x<=12)
	{
		cout<<y/2;
		return 0;
	}
	cout<<"0";
}
	

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

const int INF=1e9+5;

int main()
{
    int n;
    cin>>n;
    int h[n];
    for(int i=0;i<n;i++)
        cin>>h[i];

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


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n); for(int i = 0;i < (int)(n);i++)
#define all(x) (x).begin(),(x).end()
typedef long long ll;

int main(){
    string s;
    cin >> s;
    int n = s.size();
    int sum = 0;
    for(auto i:s)sum+=i-'0';
    cout << max(s[0]-'0'+9*(n-1)-1,sum) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long int lli;

int main() {
    int N;
    cin >> N;
    int beki = (int)log2(N);
    int temp = (int)pow(2, beki);
    cout << temp << endl;
    return 0;
}


Measured memory_bytes: 4020
var readable = process.stdin;
readable.resume();
readable.setEncoding( 'utf-8' );
readable.on( 'data', function( chunk ) {
  var data = chunk.replace( /\n/, '' ).split( ' ' );
  for( var i=0; i<data.length; i++ ) {
    data[i] = parseInt( data[i] );
  }
  for( var i=0; i<data.length-1; i++ ) {
    for( var j=i+1; j<data.length; j++ ) {
      if( data[j] < data[i] ) {
        var t = data[i];
        data[i] = data[j];
        data[j] = t;
      }
    }
  }
  console.log( data.join( ' ' ) );
} )

Measured memory_bytes: 7648
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using P = pair<int,int>;
using ll = long long;
const int INF = 100005;
const int MAX_N = 100005;

string s, t;
int a,b;
char u;


int main(){
    cin >> s;
    cin >> t;
    a = s.size();
    b = t.size();
    u = t[0];
    string ans = "";
    int count = 0;
    int num = 0;
    bool flag = false;
    bool pos = false;

    for(int i = 0; i < a-b+1; i++){
        string k = s.substr(i,b);
        //cout << k << endl;
        bool flag  = true;
        rep(j,b){
            if(k[j] != t[j] && k[j] != '?'){
                flag = false;
                break;
            }
        }
        if(flag){
            num = i;
            pos = true;
        }
    }

    if(pos){
        rep(i,num){
            if(s[i]=='?') ans += 'a';
            else ans += s[i];
        }
        ans += t;
        for(int i=num+b;i<a;i++){
            if(s[i]=='?') ans += 'a';
            else ans += s[i];
        }
        cout << ans << endl;
    }else{
        cout << "UNRESTORABLE" << endl;
    }
}



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

// 定義
typedef long long         ll;
typedef pair<ll, ll>      P;
#define ALL(x)            (x).begin(),(x).end()
#define REP(i, n)         for(ll i = 0 ; i < (ll)n ; ++i)
#define REPN(i, m, n)     for(ll i = m ; i < (ll)n ; ++i)
#define REVREP(i, n)      for(ll i = n - 1; i >= 0 ; i--)
#define VL                vector<ll>
#define VVL               vector<vector<ll>>
#define VVVL              vector<vector<vector<ll>>>
#define VC                vector<char>
#define VVC               vector<vector<char>>
#define INF               (ll)2e9
#define INF_LL            1LL<<60
//#define MOD             998244353
#define MOD               1000000007

ll Ceil(ll val, ll div)   { return (val + div - 1) / div; }
ll CeilN(ll val, ll div)  { return Ceil(val, div) * div; }
ll FloorN(ll x, ll n)     { return (x - x % n); }
bool IsOdd(ll x)          { return ((x & 1) == 1); }
bool IsEven(ll x)         { return ((x & 1) == 0); }
template<class T> bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

// 一次元累積和
template<class T>
class Ruiseki
{
private:
	int num;

public:
	vector<T> sumVal;
	Ruiseki(const vector<T> &srcVal)
	{
		num = srcVal.size();
		sumVal.resize(num + 1, 0);
		for (int i = 0; i < num; i++) {
			sumVal[i + 1] = sumVal[i] + srcVal[i];
		}
	}

	T GetSumAll()
	{
		return sumVal[num];
	}

	// [start, endIdx) ※endIdxは含まない
	T GetSumRange(int startIdx, int endIdx)
	{
		return sumVal[endIdx] - sumVal[startIdx];
	}

	// [0, endIdx) ※endIdxは含まない
	T GetSumFromTop(int endIdx)
	{
		return sumVal[endIdx] - sumVal[0];
	}

	// [startIdx, N] ※startIdxは含む
	T GetSumFromEnd(int startIdx)
	{
		return sumVal[num] - sumVal[startIdx];
	}
};

/* 次数を得る */
ll degree(ll n){
	ll degCnt = 0;
	while (n != 0) {
		n /= 2;
		degCnt++;
	}
	return degCnt;
}

void Solve()
{
	ll N, K;
	cin >> N >> K;
	VL a(N);
	REP(i, N) cin >> a[i];

	Ruiseki<ll> ruiseki(a);
	VL sum;
	REP(i, N - 1) {
		REPN(j, i + 1, N) {
			sum.emplace_back(ruiseki.GetSumRange(i, j + 1));		
		}
	}
	sort(ALL(sum), greater<ll>());

	ll deg = degree(sum.front()) - 1;
	ll ans = 0;
	for (; 0 <= deg; deg--) {
		ll bitPtn = ((ll)1 << deg);
		ll cnt = 0;
		for (auto one : sum) {
			if (one & bitPtn) cnt++;
		}
		if (K <= cnt) {
			ans |= bitPtn;
			for (auto &one : sum) {
				if (!(one & bitPtn)) one = 0;
			}
		}
	}

	cout << ans << endl;
}

// メイン
int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Solve();
	return 0;
}


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

int N, Y,A = -1,B = -1,C = -1,t = 0;

void dfs(int k,int x, int y,int z,int sum)
{
	if (t)return;
	if (sum == N) {
		if (k == Y) {
			A = x;
			B = y;
			C = z;
			t = 1;
			return;
		}
		else return;
	}
	if (k > Y)return;

	sum++;
	
	if (1000 * (N - (sum-1)) + k < Y) {
	    dfs(k+10000, x+1, y, z, sum);
		dfs(k + 5000, x, y + 1, z, sum);
	}
	else dfs(k + 1000, x, y, z + 1, sum);
}


int main()
{
	cin >> N >> Y;

	int k = 0, x = 0,n = 0;

	for (int m = 0;;) {
		if (1000 * (N - (x+10))+k + 10000*10 > Y)break;
		if (5000 * (N - (x + 1)) + k + 10000 > Y)break;

		if (m + 10000*10 < Y) {
			m += 10000*10;
			x += 10;
			k += 10000 * 10;
			n += 10;
		}
		else break;
	}

	for (int m = 0;;) {
		if (1000 * (N - (x + 1))+k + 10000 > Y)break;
		if (5000 * (N - (x + 1)) + k + 10000 > Y)break;

		if (10000+k < Y) {
			x += 1;
			k += 10000;
			n += 1;
		}
		else break;
	}

	dfs(k, x, 0, 0, n);

	cout << A << " " << B << " " << C;

	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;

typedef long long int64;
typedef pair<int, int> ii;
const int MOD = 1e9 + 7;

int main() {
    int n, a, b;
    scanf("%d", &n);
    scanf("%d", &a);
    scanf("%d", &b);

    int train = a * n;
    
    int ans = min(b, train);
    
    printf("%d\n", ans);
    
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
int main(){
  int l[99999],i,f;
  for(i=0;i<99999;i++) l[i]=0;
  while(std::cin>>i)l[i-1]++;
  for(i=0,f=0;i<99999;i++)
    if(f<l[i])f=l[i];
  for(i=0;i<99999;i++)
    if(l[i]==f)std::cout<<i+1<<"\n";
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)

int main() {
	string s;
	cin>>s;
	if(s=="ABC")cout<<"ARC";
	else cout<<"ABC";
	
	return 0;
}

Measured memory_bytes: 3596
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<complex>
#include<functional>
#include<vector>
#include<map>
#include<queue>
#include<deque>
#include<stack>
#include<set>

using namespace std;
#define endl '\n'
#define eb emplace_back
#define fst first
#define scd second
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define YES(n) cout << ((n) ? "YES" : "NO" ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No" ) << endl

constexpr long long mod = 1000000007;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<vector<ll>> vii;
typedef vector<ll> vl;

// value
ll N, A, B, C;

vl fact,fact_inv;

// 繰り返し二乗法
ll power(ll a, ll b) {
	ll res = 1LL;
	while (b > 0) {
		if (b & 1LL) res = res * a%mod;
		a = a * a%mod;
		b >>= 1LL;
	}
	return res;
}

ll comb(ll n, ll r) {
	return (fact[n] * fact_inv[r]) % mod*fact_inv[n - r] % mod;
}

void calcComb() {
	ll num = 200020LL;
    fact.resize(num);
    fact_inv.resize(num);
	fact[0] = 1LL;
	for (ll i = 0; i < num; i++) {
		fact[i + 1] = fact[i] * ((ll)i + 1LL) % mod;
	}
	fact_inv[num] = power(fact[num], mod - 2LL);
	for (ll i = num - 1LL; i >= 0; i--) {
		fact_inv[i] = fact_inv[i + 1] * ((ll)i + 1LL) % mod;
	}
}

// 逆元を求める
long long mod_inv(long long value) {

	long long b = mod, u = 1LL, v = 0LL;

	while (b) {
		long long t = value / b;
		value -= t * b;
		swap(value, b);
		u -= t * v;
		swap(u, v);
	}
	u %= mod;
	if (u < 0) u += mod;

	return u;
}

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

void solve() {

	cin >> N >> A >> B >> C;

	calcComb();

	ll ans = 0;
	for (ll M = N; M < 2 * N; M++) {
		ll X = comb(M - 1, N - 1) * ((mod_pow(A * mod_inv(100 - C) % mod, N) * mod_pow(B * mod_inv(100 - C) % mod, M - N) % mod + mod_pow(B * mod_inv(100 - C) % mod, N) * mod_pow(A * mod_inv(100 - C) % mod, M - N) % mod) % mod) % mod;
		ll Y = M * 100 % mod * mod_inv(100 - C) % mod;
		ans += X * Y % mod;
	}
	cout << ans % mod << endl;

	return;

}

signed main() {

	cin.tie(0);
	ios::sync_with_stdio(false);

	solve();

	return 0;

}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll ,ll>;
const ll INF = 1LL<<61LL;
const ll MOD = 1e9+7;

int main(){
	ll Q;
	cin >> Q;
	set<P> st;
	P before;
	ll ans = 0;
	for(int i=0;i<Q;i++){
		ll c;
		cin >> c;
		if(c == 1){
			ll a, b;
      cin >> a >> b;
			st.insert(P(a, i));
			ans += b;
			if(st.size() != 1)
				ans += abs(a - before.first);
			if(st.size() == 1)
				before = P(a, i);
			else{
				auto ite = st.find(before);
				if(st.size() % 2 && before < P(a, i)){
					ite++;
					ll nexta = ite->first;
					ll diff = nexta - before.first;
          ans -= diff;
          before = *ite;
				}else if(st.size() % 2 == 0 && before > P(a, i)){
					ite--;
					before = *ite;
				}
			}
		}else{
			cout << before.first << " " << ans << endl;
		}
	}
	return 0;
}


Measured memory_bytes: 12800
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<utility>
#include<iostream>
#include<algorithm>
#include<set>
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef long long LL;
int read()
{
	int s=0;int c=getchar(),f=1;
	while(c<48||c>57)
	{
		if(c==45) f=-1;
		c=getchar();
	}
	while(c>=48&&c<=57) s=(s<<3)+(s<<1)+(c^48),c=getchar();
	return s*f;
}
void write(LL x)
{
	if(x>=10) write(x/10);
	putchar(x%10+48);
}
void W(LL x)
{
	if(x<0) x=-x,putchar(45);
	write(x);
}
int id[111111];
set<int> sst;
int main()
{
	int N=read();
	for(int i=1;i<=N;++i) id[read()]=i;
	sst.insert(0),sst.insert(N+1),sst.insert(id[N]);
	LL Ans=0;
	for(int i=N-1;i;--i)
	{
		LL ans=0;
		set<int> ::iterator ii=sst.lower_bound(id[i]);
		int Mx=*ii,Mn=*(--ii);++ii;
		if(Mx>=1&&Mx<=N)
		{
			int Mxx=*(++ii);--ii;
//			printf("%d %d %d %d \n",Mn,id[i],Mx,Mxx);
			ans+=((LL)Mxx-Mx)*(id[i]-Mn);
		}
		if(Mn>=1&&Mn<=N)
		{
			--ii,--ii;
			int Mnn=*ii;++ii,++ii;
			ans+=((LL)Mn-Mnn)*(Mx-id[i]);
		}
//		printf("----%d\n",ans);
		Ans+=ans*i;
		sst.insert(id[i]);
	}
	printf("%lld",Ans);
	return 0;
}

Measured memory_bytes: 5376
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i ++)
using namespace std;
using ll = long long;
using PL = pair<ll,ll>;
using P = pair<int,int>;
constexpr int INF = 1000000000;
constexpr long long HINF = 1000000000000000;
constexpr long long MOD = 1000000007;// = 998244353;
constexpr double EPS = 1e-4;
constexpr double PI = 3.14159265358979;
constexpr double TL = 1.85;

clock_t start,fin;
int D;
int c[26];
int s[365][26];
int last[26];
int answer[365];
ll before_max;

ll compute_res() {
    ll ans = 0;
    vector<int> before2(26,-1);
    rep(i,D) {
        int t = answer[i];
        before2[t] = i;
        ll ret = s[i][t];
        rep(j,26) {
            ret -= (i - before2[j]) * c[j];
        }
        ans += ret;
    }
    return ans;
}

int calc_score(int d,int i) {
    int bf = last[i];
    last[i] = d;
    int res = s[d][i];
    rep(j,26) {
        res -= (d - last[j]) * c[j];
    }
    last[i] = bf;
    return res;
}

void optimization() {
    rep(d,D) {
        int max_score = -INF;
        int best_i = -1;
        rep(i,26) {
            int x = calc_score(d,i);
            if (x > max_score) {
                max_score = x;
                best_i = i;
            }
        }
        last[best_i] = d; 
        answer[d] = best_i;
    }
}

void change_day() {
    int d = rand()%D;
    int q = rand()%26;

    if (answer[d] == q) return;
    int old = answer[d];
    answer[d] = q;
    ll score = compute_res();
    if (before_max < score) return;
    else {
        answer[d] = old;
        return;
    }
}

int main() {
    clock_t start = clock();
    cin >> D;
    rep(i,26) cin >> c[i];
    rep(i,D)rep(j,26) cin >> s[i][j];
    fill(last,last + 26,-1);
    
    /*
    //答え確認用
    printf("%d\n",D);
    rep(i,26) printf("%d ",c[i]); 
    cout << '\n';
    rep(i,D){
        rep(j,26) printf("%d ",s[i][j]);
        cout << '\n';
    }
    */

    optimization();
    before_max = compute_res();
    fin = clock();
    while ((double)(fin - start)/CLOCKS_PER_SEC < TL) {
        change_day();
        fin = clock();
    }
    rep(i,D) printf("%d\n",answer[i] + 1);
    return 0;
}


Measured memory_bytes: 3760
#include <iostream>

using namespace std;

int main()
{
    int w{};
    int a{};
    int b{};
    cin >> w >> a >> b;
    int ans{max(a,b)-(min(a,b)+w)};
    if (ans<=0)
        cout << 0<< endl;
    else
        cout << ans;
    return 0;
}


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

#define rep(i, n) REP(i, 0, n)
#define repr(i, n) for (int i = (n); i >= 0; i--)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(m) cout << m << endl
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

int main()
{
    int n;
    cin >> n;
    map<string, int> mp;
    rep(i, n)
    {
        string s;
        cin >> s;
        mp[s]++;
    }
    vector<string> v;
    int maxv = 0;
    for (auto x : mp)
        maxv = max(maxv, x.second);

    for (auto x : mp)
        if (x.second == maxv)
            OP(x.first);

    return 0;
}

Measured memory_bytes: 25216
#include <stdio.h>
int main(void){
    // Your code here!
    int A,B,N,S;
     scanf("%d%d%d",&N,&A,&B);
    S=A*N;
   
    if(S<=B){
        printf("%d\n",S);
        }else{
            printf("%d\n",B);
        }
    return 0;
}


Measured memory_bytes: 128
n=int(input())
A=[]
B=[]
ans=0
for i in range(n):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)
for i in range(n-1,-1,-1):
    if (A[i]+ans)%B[i]!=0:
        ans+=(B[i]-(A[i]+ans)%B[i])

print(ans)

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

#define ll long long
#define pb push_back
#define pf push_front
#define mp make_pair
#define endl "\n" 
#define all(c) c.begin(),c.end()
#define present(c,element) (c.find(element)!=c.end())
#define cpresent(c,element) (find(c,element)!=c.end())
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll mod=1e9+7;



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

int test=1;
//cin>>test;
while(test--)
{

	int n;
	cin>>n;
	int x=n%10;
	if(x==3)cout<<"bon\n";
	else if(x==0||x==1||x==6||x==8)cout<<"pon\n";
	else cout<<"hon\n";
}
return 0;
}










Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;
int main()
  {int N, M; cin >> N >> M;
  vector<bool> bs(N + 2);
  while (M--)
    {int a; cin >> a;
    bs[a] = true;}
  vector<long long> dp(N + 2);
  dp[0] = 1;
  for (int i = 0; i < N; ++i)
    {for (int j = 1; j <= 2; ++j)
      {if (!bs[i + j]) dp[i + j] = (dp[i + j] + dp[i]) % 1000000007;}}
  cout << dp[N] << endl;}

Measured memory_bytes: 1024
#include <stdio.h>
#include <queue>
using namespace std;
typedef long long ll;

int main(void) {
  ll i, j, q, now = 0, a, b, c, s1 = 0, s2 = 0;
  scanf("%lld", &q);
  priority_queue<ll> q1;
  priority_queue< ll, vector<ll>, greater<ll> > q2;
  for(i = 0; i < q; ++i) {
    scanf("%lld", &a);
    if(--a) 
      printf("%lld %lld\n", q1.top(), now + (q1.size() - q2.size()) * q1.top() - s1 + s2);
    else {
      scanf("%lld%lld", &b, &c);
      now += c;
      if(!q1.size() || q1.top() > b) q1.push(b), s1 += b;
      else q2.push(b), s2 += b;
      if(q1.size() > q2.size() + 1) s1 -= q1.top(), s2 += q1.top(), q2.push(q1.top()), q1.pop();
      else if(q1.size() < q2.size()) s2 -= q2.top(), s1 += q2.top(), q1.push(q2.top()), q2.pop();
    }
  }
  return 0;
}

Measured memory_bytes: 3828
N, M, X = map(int, input().split())
A = []
C = []
for _ in range(N):
    temp = list(map(int, input().split()))
    C.append(temp[0])
    A.append(temp[1:])
# print(A)

ans = 10 ** 7
flag = False
for i in range(1, 2 ** N):
    cost = 0
    under = [0] * M
    for j in range(N):
        if ((i >> j) & 1):
            cost += C[j]
            for k in range(M):
                under[k] += A[j][k]
    if all([val >= X for val in under]):
        ans  = min(ans, cost)
        flag = True
if flag:
    print(ans)
else:
    print(-1)


Measured memory_bytes: 68896
/*
   Creator - Glitched
   Yeet!!
*/
#include "bits/stdc++.h"
using namespace std;

#define testcases ll T;cin>>T;while(T--)
#define ll long long
#define loop(i,x,n) for(ll i=x;i<n;i++)
#define loopr(i,x,n) for(ll i=n-1;i>=x;i--)
#define ff first
#define ss second
#define pb push_back
#define elif else if
#define flush cout<<"\n"
#define mod 1E9+7
#define L LONG_MAX
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
const string yes = "Yes", no = "No";
ll dp[101][101];
char a[101][101];

ll f(ll i, ll j, ll count, ll n, ll m){
	if(a[i][j] == '#')
		count++;
	// if(dp[i][j] != -1){
	// 	return dp[i][j];
	// }

	if(i == n-1 && j == m-1){		
		return count;		
	}

	if(i == n-1){
		dp[i][j]  =  f(i, j+1, count, n,m);
		return dp[i][j];
	}
	if(j == m-1){
		dp[i][j]=f(i+1,j, count, n , m);
		return dp[i][j];
	}
	dp[i][j] = min(f(i,j+1,count,n,m), f(i+1,j,count,n,m));
	return dp[i][j];

}


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

	ll ans =0;

	if(n>1){
		ans += ((n-1)*n)/2;
	}
	if(m>1){
		ans += ((m-1)*m)/2;
	}
	cout<<ans;
}

Measured memory_bytes: 256