akhauriyash/Code-Regression huggingface dataset:
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9 + 7
ans = 0
for i in range(n):
    cnt = 0
    cnt2 = 0
    for j in range(n):
        if a[i] > a[j]:
            cnt += 1
            if i < j:
                cnt2 += 1
    ans += (cnt*(k-1)*k//2 % mod) + cnt2*k
    ans %= mod
    # print(ans, cnt)
print(ans)


Measured memory_bytes: 3188
//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<utility>
#include<algorithm>
#include<cstring>
#include<sstream>
#include <iomanip>

using namespace std;

typedef long long ll ;
typedef double db;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector< pair<int,int> > vii;
const double pi = 2*acos(0) ;

#define pf		  	printf
#define sf			  scanf
#define pb(a)         push_back(a)
#define mp			make_pair
#define fi			 first
#define se			 second
#define for0(i,n)        for(int i=0;i<n;i++)
#define for1(i,n)        for(int i=1;i<=n;i++)
#define forab(i,a,b)       for(int i=a;i<=b;i++)
#define lcm(a, b)     ((a)*((b)/gcd(a,b)))
#define sq(a)		   (a)*(a)
#define nw				"\n"
#define abs(x)		fabs(x)
#define pcase(z,x)    cout<<"Case "<<z<<": "<<x<<"\n"
int main()
{
	ll dp[90];
	dp[0] = 2;
	dp[1] = 1;
	ll n;
	cin>>n;
	for(ll i=2 ; i<=n ; i++) dp[i] = dp[i-1] + dp[i-2];
	cout<<dp[n]<<nw;
	return 0;
}

Measured memory_bytes: 256
line = gets.split(' ').map(&:to_i)

if line == [0, 0, 0, 0]
  puts 0
  exit
end

f = line[0,2]
s = line[2,2]

line.reject!{|x| x == 0}
f.reject!{|x| x == 0}
s.reject!{|x| x == 0}
arr = []
f.each do |x|
  s.each do |y|
    arr << x * y
  end
end

puts arr.max

Measured memory_bytes: 14412
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define MOD 1000000007
using Graph = vector<vector<int>>;
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
namespace mp = boost::multiprecision;
// 任意長整数型
using Bint = mp::cpp_int;
// 仮数部が1024ビットの浮動小数点数型(TLEしたら小さくする)
using Real = mp::number<mp::cpp_dec_float<1024>>;
 
int main (){
  int N;
  cin>>N;
  vector<long long>A(N);
  rep(i,N) cin>>A[i];
  long long souwa=0;
  rep(i,N){
    souwa+=A[i];
    souwa=souwa%MOD;
  }
  long long ans=0;
  rep(i,N-1){
    souwa=(souwa-A[i]+MOD)%MOD;
    ans+=A[i]*souwa;
    ans=ans%MOD;
  }
  cout<<ans;
}

Measured memory_bytes: 4836
H, W = map(int, input().split())
BOARD = []

for _ in range(H):
    BOARD.append(list(map(int, input().split())))

ans = []
# (0, 0), (0, 1), (0, 2), ..., (0, W), (1, W), (1, W-1), ..., (1, 0), (2, 0), ...
# のように見ていって奇数なら次のマスへうつす
move = False
prev_h = -1
prev_w = -1
for h in range(H):
    for w in (range(W) if h % 2 == 0 else reversed(range(W))):
        if move:
            ans.append((prev_h, prev_w, h, w))
            BOARD[prev_h][prev_w] -= 1
            BOARD[h][w] += 1
        cnt = BOARD[h][w]
        move = cnt % 2 == 1
        prev_h, prev_w = h, w
# print(BOARD)

# 出力
print(len(ans))
for row in ans:
    print(' '.join([str(r + 1) for r in row]))


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

using namespace std;
void cn(vector<int> a) 
{ 
  
    int n = a.size(); 
  
    int count = 0;
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            for(int k=j+1;k<n;k++)
            {
                if(a[i]+a[j]>a[k] && a[j]+a[k]>a[i] && a[k]+a[i]>a[j] && a[i]!=a[j] && a[j]!=a[k] && a[i]!=a[k])
                count++;
            }
        }
    }
    cout<<count;
}
int main()
{
    int n;
    cin>>n;
    vector<int> a;
    for(int i=0;i<n;i++)
    {
        int r;
        cin>>r;
        a.push_back(r);
    }
    cn(a);
   return 0;
}

Measured memory_bytes: 3592
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const int SZ = 200005;
const ll INF = 200000000000005LL;
ll arr[SZ];
ll pre[SZ];
pll mm(int l, int r){
	ll xx = INF,mn,mx;
	int lx = l, rr = r;
	while(lx<=rr){
		int m = (lx+rr)/2;
		ll tmp = pre[r]-pre[m]-(pre[m]-pre[l-1]);
		if(abs(tmp)<xx){
			xx=abs(tmp);
			mn = pre[r]-pre[m];
			mx = pre[m]-pre[l-1];
			if(mx<mn) swap(mn,mx);
		}
		if(tmp>0LL) lx=m+1;
		else rr=m-1;
	}
	return make_pair(mn,mx);
}
int main(void){
	int n; scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&arr[i]);
	for(int i=1;i<=n;i++) pre[i]=pre[i-1]+arr[i];
	ll ans = INF;
	for(int i=2;i<=n-2;i++){
		pll x = mm(1,i); pll y = mm(i+1,n);
		ll mn = min(x.first,y.first);
		ll mx = max(x.second,y.second);
		ans = min(mx-mn,ans);
	}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 3328
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;
 
int main () {
	int n,max,min,t;
	cin >> n;
	cin >> t;
	max = min = t;

	for (int i=0;i<n-1;i++){
		cin >> t;
		if(t>max)max=t;
		if(t<min)min=t;
	}

	cout << max - min << endl;



    return 0;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))

ans = 0
for j in range(60):
    odd = 0
    even = 0
    for i in range(n):
        if a[i] % 2 == 0:
            even += 1
        else:
            odd += 1
    ans += even * odd * 2**j
    a = [i//2 for i in a]
    ans %= 10**9+7

print(ans)


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

int main() {
  string A, B;
  cin >> A >> B;

  cout << (A.at(0) == B.at(2) && A.at(1) == B.at(1) && A.at(2) == B.at(0) ? "YES" : "NO") << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

using namespace std;

using ull_t = unsigned long long;

struct ticket_t { long x, y, c; };

int main()
{
    long NA, NB, NM;
    cin >> NA >> NB >> NM;

    vector<long> A(NA), B(NB);
    for (int i = 0; i < NA; ++i)
        cin >> A[i];
    for (int i = 0; i < NB; ++i)
        cin >> B[i];
    
    vector<ticket_t> M(NM);
    for (int i = 0; i < NM; ++i)
    {
        cin >> M[i].x >> M[i].y >> M[i].c;
        --M[i].x;
        --M[i].y;
    }

    int x_min =
        (*min_element(A.begin(), A.end())) +
        (*min_element(B.begin(), B.end()));
    for (const auto &m : M)
    {
        int x = A[m.x] + B[m.y] - m.c;
        x_min = min(x, x_min);
    }

    cout << x_min << endl;
}


Measured memory_bytes: 4096
/**
*    created: 14.05.2020 14:18:40
**/
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using namespace std;

signed main() {

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

    string s; cin >> s;
    if (s == "A") cout << "T" << endl;
    if (s == "C") cout << "G" << endl;
    if (s == "G") cout << "C" << endl;
    if (s == "T") cout << "A" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(void) {
	const int z = 3;
	bool jud = true;
	int a[z][z],a1,a2,a3,b1,b2,b3;
	for (int i = 0; i < z; i++) {
		for (int j = 0; j < z; j++) {
			cin >> a[i][j];
		}
	}
	for (int i = -100; i < 100; i++) {
		a1 = i;
		b1 = a[0][0] - a1;
		b2 = a[0][1] - a1;
		b3 = a[0][2] - a1;
		a2 = a[1][0] - b1;
		a3 = a[2][0] - b1;
		if(a2+b2!=a[1][1]||a2+b3!=a[1][2]||a3+b2!=a[2][1]||a3+b3!=a[2][2])
		{jud = false;}
		else { jud = true; break; }
	}
	if (jud == true) { cout << "Yes"; }
	else { cout<<"No"; }
	return 0;
}

Measured memory_bytes: 256
//inlclude前用define 
#define _USE_MATH_DEFINES

//include
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<type_traits>
#include<numeric>
//#include<deque>
#include<iomanip>
#include<set>
#include<tuple>
#include<map>
#include<limits>

using namespace std;

//typedef
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<char> VC;
typedef long long int ll;

//define
#define INF 1e9 
#define NUM 1000000007
#define all(x) begin(x), end(x)
#define rep(i,n) for(int i=0;i<(int)(n);i++)

int main(){
  int n,k;
  cin>>n>>k;
  VI a(n);
  map<int,double> mp;
  int maxv=-1;
  rep(i,n){
    cin>>a[i];
    mp[a[i]]=-1;
    maxv=max(maxv,a[i]);
  }
  double sum=0;
  for(int i=1;i<=maxv;i++){
    sum+=i;
    if(mp[i]<0){
      mp[i]=sum/i;
    }
  }
  //for(const auto & x:mp) cout<<x.first<<" "<<x.second<<endl;

  int cnt=0;
  double ans=-1,sum_v=0;
  rep(i,k) sum_v+=mp[a[i]];

  ans=max(sum_v,ans);
  for(int i=k;i<n;i++){
    sum_v-=mp[a[i-k]];
    sum_v+=mp[a[i]];
    ans=max(sum_v,ans);
  }
  cout<<fixed;
  cout<<setprecision(10)<<ans<<endl;
}


Measured memory_bytes: 1152
let () =
  let replace s1 s2 =
    Str.global_replace (Str.regexp_string s1) s2
  in
  let line = read_line () in
  replace "apple" "APPLE" line
  |> replace "peach" "apple"
  |> replace "APPLE" "peach"
  |> print_endline
;;

Measured memory_bytes: 2048
#include<stdio.h>

int main()
{
	int build[4][3][10];
	int i, j, k;
	for(i = 0; i < 4; i++)
	{
		for(j = 0; j < 3; j++)
		{
			for(k = 0; k < 10; k++)
			{
				build[i][j][k] = 0;
			}
		}
	}
	
	int n = 0;
	scanf("%d", &n);
	while(n--)
	{
		int b, f, r, v;
		scanf("%d %d %d %d", &b, &f, &r, &v);
		build[b - 1][f - 1][r - 1] += v;
	}
	for(i = 0; i < 4; i++)
	{
		for(j = 0; j < 3; j++)
		{
			for(k = 0; k < 10; k++)
			{
				printf(" %d", build[i][j][k]);
			}
			printf("\n");
		}
		if(i != 3)
		{
			printf("####################\n");
		}
	}
	
	return 0;
}


Measured memory_bytes: 2616
/************************************************************LET US BREAK BAD!****************************************************************/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long int
#define ld long double
#define pb push_back
#define pll pair<ll, ll> 
#define vi vector<int>
#define vl vector<ll> 
#define vvl vector< vector<ll> > 
#define vvi vector< vector<int> >
#define vlp vector< pair<ll, ll> >
#define vllp vector<pair<ll, ll>, ll > 
#define mll map<ll, ll> 
#define rep(i,a)  for(ll i=0; i< a; i++)
#define rep1(i,a)   for(ll i = 1; i< a; i++)
#define foi(i, a, b)    for(ll i = a; i<b ; i++)
#define fod(i, a, b)    for(ll i = a; i>=b ; i--)
#define mp make_pair
#define fst first
#define sec second
#define ff first.first
#define fs first.second
#define pi pair<int, int>
#define ppi pair<pair<int, int>, int>
#define max3(a, b, c)   max(max(a, b), c)
#define min3(a, b, c)   min(min(a, b), c)
#define MAX 1000001
#define MOD 1000000007
// #define MOD 998244353
#define endl "\n"
#define INF (ll)1e18
#define s(v) v.size()
#define e(v) v.empty()
#define bscount(x) __builtin_popcountll(x)
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

using namespace std;
using namespace __gnu_pbds;

ll gcd(ll a, ll b){if(b==0)return a;return gcd(b, a%b);}
ll lcm(ll a, ll b){return a*b/gcd(a, b);}
ll fexp(ll a, ll b){ll ans = 1;while(b){if(b&1) ans = ans*a%MOD; b/=2;a=a*a%MOD;}return ans;}
ll inverse(ll a, ll p){return fexp(a, p-2);} 
void ingraph(vvl& graph, ll m){ll x, y;rep(i, m){cin>>x>>y;x--, y--;graph[x].pb(y);graph[y].pb(x);}}
ll modify(ll n){ll res = n;res%=MOD;res+=MOD;res%=MOD;return res;}

int main(){
    //#ifndef ONLINE_JUDGE
    //    freopen("../input.txt", "r", stdin);
    //    freopen("../output.txt", "w", stdout);
    //#endif
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll t;
    // cin>>t;
    t = 1;
    while(t--){
        string ss;
        cin>>ss;
        ll len = ss.length();
        ll ans = 0;
        rep(i, len){
            ans+=ss[i]-'0';
        }
        if(ans%9){
            cout<<"No"<<endl;
        }
        else{
            cout<<"Yes"<<endl;
        }
    }
return 0;
}


Measured memory_bytes: 3740
N, M = list(map(int, input().split()))

res = ['0'] * N
fixed = [False] * N
if N != 1:
  res[0] = '1'

for i in range(M):
  s, c = list(map(int, input().split()))
  if N < s:
    res = ['-1']
    break
  s-=1
  c = str(c)
  if fixed[s] and c != res[s]:
    res = ['-1']
    break
  fixed[s] = True
  res[s] = c

if N != 1 and res[0] == '0':
  res = ['-1']

print(''.join(res))

Measured memory_bytes: 38384
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;

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

int R, S, P;
int func(char w){
    int val;
    if(w == 'r') val = R;
    if(w == 's') val = S;
    if(w == 'p') val = P;
    return val;
}

int main(){
    int N, K;
    cin >> N >> K;
    cin >> R >> S >> P;
    string T;
    string S;
    cin >> T;
    rep(i, N){
        if(T[i] == 'r') S.push_back('p');
        if(T[i] == 's') S.push_back('r');
        if(T[i] == 'p') S.push_back('s');
    }
    ll ans = 0;
    rep(i, N){
        if(i < K) ans += func(S[i]);
        else{
            if(S[i] == S[i-K]){
                S[i] = 'F';
            }else{
                ans += func(S[i]);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3732
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
typedef long long ll;
long long mod = 1e9 + 7;
const long long INF = 1LL << 60;
using namespace std;

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

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

int main()
{
    while (true)
    {
        int n, x;
        cin >> n >> x;
        if (n == 0 && x == 0)
            break;

        int ans = 0;
        repi(i, 1, n + 1) repi(j, i + 1, n + 1) repi(k, j + 1, n + 1)
        {
            if (i + j + k == x)
                ans++;
        }

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


Measured memory_bytes: 3092
# -*- coding: utf-8 -*-
N, X = map(int, input().split())
L = list(map(int, input().split()))
D = [0] * 1 
Dtemp = 0

for i in range(0, N):
	Dtemp = D[i] + L[i]
	if len(D) > N + 1:
		print(N + 1)
		exit()
	elif Dtemp > X:
		print(len(D))
		exit()
	else:
		D.append(Dtemp)

print(len(D))

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int a[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  int n;
  cin>>n;
  cout<<a[n-1]<<endl;
}

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

int main() {
  int n;
  cin >> n;
  while (n--) {
    float x[4], y[4];
    for (int i = 0; i < 4; i++) {
      cin >> x[i] >> y[i];
    }
    // if((x2-x1)*(y4-y3)==(x4-x3)*(y2-y1))cout<<"YES"<<endl;
    if ((x[1] - x[0]) * (y[3] - y[2]) == (x[3] - x[2]) * (y[1] - y[0])) {
      cout << "YES" << endl;
    } else {
      cout << "NO" << endl;
    }
  }
}

Measured memory_bytes: 1224
#include <algorithm>
#include <iostream>
#include <vector>

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

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    std::vector<int> sorted = a;
    std::sort(sorted.begin(), sorted.end(), std::greater<int>());
    int max = sorted[0], second_max = sorted[1];

    for (int i = 0; i < n; i++) {
        std::cout << (a[i] == max ? second_max : max) << std::endl;
    }
}


Measured memory_bytes: 3200
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = Integer.parseInt(scan.next());
		int D = Integer.parseInt(scan.next());
		int[] X = new int[N];
		int[] Y = new int[N];
		int ans = 0;
		for (int n = 0;n < N ;n++ ) {
			X[n] = Integer.parseInt(scan.next());
			Y[n] = Integer.parseInt(scan.next());
			long xx = (long)Math.pow(X[n], 2);
			long yy = (long)Math.pow(Y[n], 2);
			if (Math.sqrt(xx + yy) <= D) {
				ans++;
			}
		}
		scan.close();
		System.out.println(ans);
	}

}


Measured memory_bytes: 61584
#include <bits/stdc++.h>
#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 ALL(x) (x).begin(), (x).end()
const long long INF = 1e15;
using namespace std;
typedef long long ll;
int main() {
  ll a, b;
  cin >> a >> b;
  ll ans = a - 2 * b;
  if (ans < 0) ans = 0;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int k, a, b;
  cin >> k >> a >> b;
  for(int i = a; i <= b; ++i){
    if(i % k == 0){
      cout << "OK" << endl;
      return 0;
    }
  }
  cout << "NG" << endl;
}


Measured memory_bytes: 3548
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll 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(ll 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) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
}comb(100005);
mint permutation(int n, int r) {
  if(n < 0) return 0; 
  mint res = comb(n, r);
  res *= comb.fact[r];
  return res;
}

int n, k;
vector<vector<int>> graph;

mint ans;
void dfs(int v, int pre=-1) {
  for (int u: graph[v]) {
    if(u == pre) continue;
    dfs(u, v);
  }
  int nn = (pre==-1) ? k : k - 2;
  int kk = (pre==-1) ? graph[v].size() + 1 : graph[v].size() - 1;
  ans *= permutation(nn, kk);
}

int main() {
  
  cin >> n >> k;
  graph.resize(n);
  rep(i, n - 1) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }

  ans = 1;
  dfs(0);
  cout << ans << endl;
}

Measured memory_bytes: 10752
import math
n,m,k=map(int,input().split())
mod=10**9+7
s=math.factorial(n*m-2)//(math.factorial(n*m-k)*math.factorial(k-2))
cnt=0
s%=mod
a=(m*m*s)%mod
for d in range(1,n):
        cnt+=d*(n-d)*a
        cnt%=mod
a=(n*n*s)%mod
for d in range(1,m):
        cnt+=d*(m-d)*a
        cnt%=mod
print(cnt)

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

int main() {
  int n, sum=0;
  cin >> n;
  vector<int> l(n);
  for(int i = 0;i < n;i++){
  	cin >> l.at(i);
  }
  sort(l.begin(), l.end());
  for(int i = 0;i < n-2;i++){
    for(int j = i+1;j < n-1;j++){
      for(int k = j+1;k<n;k++){
        if(l.at(k) < l.at(j) + l.at(i)){
          sum++;
        }
      }
    }
  }
  cout << sum << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
typedef unsigned long long ll;
#define rep(i, n) for (int i=0;i < (int)(n);i++)


int main(){
     string s,t,u;
     cin >> s >> t >> u;
     int a=0,b=0,c=0;
     char ans[]={'A','B','C'};
     int n=1;
     int id;
     while (1){
         switch(n){
             case 1:{
                 if (a==s.size()){
                     id=0;
                     cout << ans[id] << endl;
                     return 0;
                 }
                 switch(s[a]){
                     case 'a':n=1;break;
                     case 'b':n=2;break;
                     case 'c':n=3;break;
                 }
                 a++;
                 break;
             }
             case 2:{
                 if (b==t.size()){
                     id=1;
                     cout << ans[id] << endl;
                     return 0;
                 }
                 switch(t[b]){
                     case 'a': n=1;break;
                     case 'b':n=2;break;
                     case 'c':n=3;break;
                 }
                 b++;
                 break;
             }
             case 3:{
                 if (c==u.size()){
                     id=2;
                     cout << ans[id] << endl;
                     return 0;
                 }
                 switch(u[c]){
                     case 'a': n=1;break;
                     case 'b':n=2;break;
                     case 'c':n=3;break;
                 }
                 c++;
                 break;
             }
         } 
        // printf("next  is %c\n",ans[n-1]);
        //printf("a:%d   b:%d  c:%d\n",a,b,c);

     }

    
}


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

int main() {
    int k;
    cin>>k;
    int count = 0;
    int temp = 0;
    for(int i=1;i<=k;++i){
        temp = (temp%k)*10 + 7;
        count++;
        if(temp%k==0){
            cout<<count;
            return 0;
        }
    }
    cout<<-1;
    return 0;
}


Measured memory_bytes: 3572
#include <iostream>
#include <vector>
#include <string>
using namespace std;

char c[100][100];
char c1[200][100];

int main(void){
    // Your code here!
    int n, m;
    cin>>n;
    vector<int> t(n);
    
    for(int i=0; i<n; i++){
        cin>>t[i];
    }
    
    cin>>m;
    vector<int> p(m), x(m);
    
    
    for(int i=0; i<m; i++){
        cin>>p[i]>>x[i];
    }
    
    int sum=0;
    for(int i=0; i<n; i++){
        sum+=t[i];
    }
    
    for(int i=0; i<m; i++){
        int temp;
        
        temp=sum-t[p[i]-1]+x[i];
        cout<<temp<<endl;
    }
}


Measured memory_bytes: 256
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

N = I()
a = III()

x = defaultdict(int)

for i in range(N):
    x[a[i]] += 1

ans = 0
for k in x.keys():
    if x[k]<k:
        ans += x[k]
    else:
        ans += x[k]-k

print(ans)

Measured memory_bytes: 65056
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())
#define ll long long
#define pb(a) push_back(a)
#define INF 1000000000
#define LINF 1e18
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

typedef vector<unsigned int>vec;
typedef vector<vec> mat;

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

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const double PI = acos(-1.0);
const double EPS = 1e-10;

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

    string mae,ushi;
    mae = S.substr(0,N);
    ushi = S.substr(N,N);

    map<pair<string,string>,ll> mp;
    //後ろ半分の文字列(反転させる)
    for(int i=0;i<(1<<N);i++){
        string a="",b="";
        for(int j=0;j<N;j++){
            if(i>>j & 1) a += ushi[j];
            else b += ushi[j];
        }
        reverse(a.begin(),a.end());
        reverse(b.begin(),b.end());
        auto p = make_pair(a,b);
        ++mp[p];
    }

    ll res = 0;
    for(int i=0;i<(1<<N);i++){
        string a="",b="";
        for(int j=0;j<N;j++){
            if(i>>j & 1) a += mae[j];
            else b += mae[j];
        }
        auto p = make_pair(a,b);
        res += mp[p];
    }
    cout<<res<<endl;
}


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

#define all(a) a.begin(), a.end()
#define ff first
#define ss second
#define pb push_back

using ll = long long;
using pii = pair<int, int>;

template<typename T> using V = vector<T>;

const int N = 2e5 + 10;
ll add[N], ans[N];
vector<int> adj[N];

void dfs(int cur, int par) {
	ans[cur] += add[cur];
	for (auto nxt : adj[cur]) {
		if (nxt == par)
			continue;
		add[nxt] += add[cur];
		dfs(nxt, cur);
	}
}

int main() {
	ios::sync_with_stdio(false);cin.tie(nullptr);
	int n, q; cin >> n >> q;
	for (int i = 1; i < n; ++i) {
		int a, b; cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	while (q--) {
		int x, p; cin >> p >> x;
		add[p] += (ll)x;
	}
	dfs(1, 0);
	for (int i = 1; i <= n; ++i) {
		cout << ans[i] << " \n"[i == n];
	}
}

Measured memory_bytes: 25856
import java.util.*;
public class Main{
	public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] a = new int[n+1];
        for(int i=0; i<n; i++){
            int s = sc.nextInt();
            a[s]++;
        }
        Arrays.sort(a);
        int ans = 0;
        for(int i=0; i<a.length-k; i++){
            ans += a[i];
        }
        System.out.println(ans);
    }
    
}

Measured memory_bytes: 84492
#include<iostream>

int main(){
    int n, y;
    std::cin >> n >> y;
    y /= 1000;

    for(int a = 0; a <= 2000; a++){
        for(int b = 0; b <= 4000; b++){
            int c = n - a - b;
            if(0 <= c && c <= 20000 && 10*a + 5*b + c == y){
                std::cout << a << " " << b << " " << c << std::endl;
                return 0;
             }
        }
    }

    std::cout << -1 << " " << -1 << " " << -1 << std::endl;
    return 0;
}

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

int main(){
	int n;
	cin >> n;
	int a[n];
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	int count = 0;
	for(int i = 0; i < n; i++){
        int minj = i;
		for(int j = i+1; j < n; j++){
			if(a[j] < a[minj]){
                minj = j;
            }
        }
        if(minj == i){
            continue;
        }
        else{
            swap(a[i], a[minj]);
            count++;
        }
    }
	for(int i = 0; i < n; i++){
		if(i == 0){
			cout << a[i];
		}
		else{
			cout << ' ' << a[i];
		}
	}
	cout << endl <<  count << endl;
}



Measured memory_bytes: 3064
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
#define _USE_MATH_DEFINES
#include<math.h>
#include<numeric>
#include<iomanip>

using namespace std;

int main() {
	int n, m; cin >> n >> m;
	vector<int>a(n), b(n), c(m), d(m);
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
	}
	for (int i = 0; i < m; i++) {
		cin >> c[i] >> d[i];
	}
	unsigned long long int tmp = pow(10, 9);
	int tmpj = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			//int g= abs(a[i] - c[j]) + abs(b[i] - d[j]);
			//cout << g << endl;
			if (tmp > abs(a[i] - c[j]) + abs(b[i] - d[j])) {
				tmp = abs(a[i] - c[j]) + abs(b[i] - d[j]);
				//cout << "a" << endl;
				tmpj = j+1;
			}
		}
		cout << tmpj << endl;
		tmp = pow(10, 9);
	}
}









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

#define MIN_INT -2147483648
#define MAX_INT 2147483647
#define MIN_LONG -9223372036854775808L
#define MAX_LONG 9223372036854775807L

#define long long long int

using namespace std;

// @author: pashka

int main() {
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    vector<int> a(2 * n);
    for (int i = 0; i < 2 * n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    int res = 0;
    for (int i = 0; i < n; i++) {
        res += a[2 * i];
    }
    cout << res;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v).begin(), (v).end()
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define DEBUG
#define int long long
#define INF 1e9
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }
template<class T>void show(vector<T>v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<"\n";}
typedef long long ll;

int a[10010];
signed main(){
    int k,t;
    cin>>k>>t;
    REP(i,t) cin>>a[i];
    sort(a,a+t,greater<int>());
    if(a[0]-(k+1)/2<=0){
        cout<<0<<endl;
    }
    else{
        cout<<2*(a[0]-(k+1)/2-1)+1<<endl;
    }
    
     
   
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

int n,k;
int h[100001];
int main(){
    cin>>n>>k;
    rep(i,n) cin>>h[i];
    sort(h,h+n);
    int mn=1000100010;
    rep(i,n-k+1){
        mn=min(mn,h[i+k-1]-h[i]);
    }
    cout<<mn<<endl;
    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    int h[n+1][4];
    for(int i=1;i<=n;i++)
        cin >> h[i][1] >> h[i][2] >> h[i][3];
    int dp[n+1][4] ={0,};
    memset(dp,0,sizeof(dp));
    dp[1][1] = h[1][1];
    dp[1][2] = h[1][2];
    dp[1][3] = h[1][3];
    for(int i=2;i<=n;i++){
            dp[i][1] = max(dp[i-1][2] + h[i][1] , dp[i-1][3] + h[i][1]);
            dp[i][2] = max(dp[i-1][1] + h[i][2] , dp[i-1][3] + h[i][2]);
            dp[i][3] = max(dp[i-1][1] + h[i][3],dp[i-1][2]+ h[i][3]);
    }
    cout<< max(max(dp[n][1],dp[n][2]),dp[n][3]) <<endl;

}

Measured memory_bytes: 3328
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::io::{stderr, stdin, stdout, BufRead, BufWriter, Read, StdoutLock, Write};
#[allow(unused_imports)]
use std::iter::FromIterator;
#[allow(unused_imports)]
use std::{i64, u64, usize};
#[allow(unused_macros)]
/// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules !input {(source =$s :expr ,$($r :tt ) *) =>{let mut iter =$s .split_whitespace () ;input_inner !{iter ,$($r ) *} } ;($($r :tt ) *) =>{let mut s ={use std ::io ::Read ;let mut s =String ::new () ;std ::io ::stdin () .read_to_string (&mut s ) .unwrap () ;s } ;let mut iter =s .split_whitespace () ;input_inner !{iter ,$($r ) *} } ;}
#[allow(unused_macros)]
macro_rules !input_inner {($iter :expr ) =>{} ;($iter :expr ,) =>{} ;($iter :expr ,$var :ident :$t :tt $($r :tt ) *) =>{let $var =read_value !($iter ,$t ) ;input_inner !{$iter $($r ) *} } ;}
#[allow(unused_macros)]
macro_rules !read_value {($iter :expr ,($($t :tt ) ,*) ) =>{($(read_value !($iter ,$t ) ) ,*) } ;($iter :expr ,[$t :tt ;$len :expr ] ) =>{(0 ..$len ) .map (|_ |read_value !($iter ,$t ) ) .collect ::<Vec <_ >>() } ;($iter :expr ,chars ) =>{read_value !($iter ,String ) .chars () .collect ::<Vec <char >>() } ;($iter :expr ,usize1 ) =>{read_value !($iter ,usize ) -1 } ;($iter :expr ,$t :ty ) =>{$iter .next () .unwrap () .parse ::<$t >() .expect ("Parse error" ) } ;}
#[allow(unused_macros)]
macro_rules !dbg {($($a :expr ) ,*) =>{writeln !(&mut stderr () ,concat !($(stringify !($a ) ," = {:?}, " ) ,*) ,$($a ) ,*) .unwrap () ;} }
#[allow(non_snake_case)]
#[allow(dead_code)]
fn main() {
    input! {
        h: u64,
        w: u64,
    }
    if h == 1 || w == 1 {
        println!("{}", 1);
        return;
    }
    let ans: u64 = ((h + 2 - 1) / 2) * ((w + 2 - 1) / 2) + (h / 2) * (w / 2);
    println!("{}", ans);
}

Measured memory_bytes: 4352
#include<stdio.h>
#include<algorithm>
int n;
int a[1001];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    std::sort(a+1,a+n+1);
    printf("%d",a[n]-a[1]);
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;++i)
#include<string>
using namespace std;
typedef long long ll;
//max=({});
//条件式が真ならwhileの中身を回し続ける

bool flag[1050000];

int main() {
	string s;
	cin >> s;
	int L = s.length();
	rep(i, L) {
		s[i] = 'x';
	}
	cout << s << endl;
	return 0;
}


Measured memory_bytes: 256
import std.stdio, std.conv, std.array, std.string, std.algorithm, std.container, std.range, core.stdc.stdlib, std.math, std.typecons;
T[][] combinations(T)(T[] s, in int m) {   if (!m) return [[]];   if (s.empty) return [];   return s[1 .. $].combinations(m - 1).map!(x => s[0] ~ x).array ~ s[1 .. $].combinations(m); }

void main() {
  auto N = readln.chomp.to!(ulong);

  void solve() {
    ulong answer;
    ulong keta = 1;
    ulong[ulong] ht_set;
    foreach(i; 11..100) ht_set[i] = 0;

    foreach(i; 1..N+1) {
      auto tail = i % 10;
      if (tail == 0) {
        keta = i.to!(string).length;
        continue;
      }

      auto head = i / 10.pow(keta - 1);
      auto htkey = head*10 + tail;

      if (head == tail) {
        answer += ht_set[htkey] * 2 + 1;
      } else {
        auto inverted_key = tail*10 + head;
        answer += ht_set[inverted_key] * 2;
      }
      
      ht_set[htkey]++;

      auto inverted = i % 10.pow(keta - 1);
      inverted -= inverted % 10;
      inverted += head + tail * 10.pow(keta - 1);
      if (inverted <= i) {
      }
    }

    answer.writeln();
    // ht_set.writeln();
  }

  solve();
}


Measured memory_bytes: 636
h, w = map(int, input().split())
S = [list(input()) for i in range(h)]
for i in range(h):
    for j in range(w):
        if S[i][j] == '#':
            continue
        cnt = 0
        for dx in [-1, 0, 1]:
            for dy in [-1, 0, 1]:
                if not 0 <= i+dy < h or not 0 <= j+dx < w:
                    continue
                if S[i+dy][j+dx] == '#':
                    cnt += 1
        S[i][j] = str(cnt)
for s in S:
    print("".join(s))

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
 
typedef vector<int> vi;;
typedef vector<ll> vll;

#define l() length()
#define sz() size()
 
#define b() begin()
#define e() end()
#define all(x) x.begin(), x.end()
 
#define pb(i) push_back(i)
#define PB() pop_back()
 
 
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;
#define mp make_pair
#define Fi first
#define Se second
 
const int maxx=1e6+9;
 
// Happy Coding!

struct Point{
public:
    int x,y;
    Point(int x,int y){
        this->x=x;
        this->y=y;
    }
};

double square(double x){return x*x;}
double distance(Point p1,Point p2){return sqrt( square(p1.x-p2.x) + square(p1.y-p2.y) );}

int factorial(int n){
    int f=1;
    for(int i=1;i<=n;i++){f*=i;}
    return f;
}
void solve(){
    int n;
    cin>>n;
    
    vector<Point> arr;
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        arr.push_back(Point(x,y));
    }
    
    vi sequence(n); // gives the sequence of the indices 
    for(int i=0;i<n;i++){sequence[i]=i;}
    
    double sum=0.0;
    do{
        for(int i=0;i<n-1;i++){
            sum+=distance(arr[sequence[i]],arr[sequence[i+1]]);
        }
    }while(next_permutation(sequence.b(),sequence.e()));
    
    
    cout<<setprecision(12)<<sum/factorial(n);
}

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

Measured memory_bytes: 3784
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll ZERO = 0;
const int Inf = 1e9;
const ll INF= 1e18;
const ll MOD = 1000000007;
const double PI = 3.1415926535897;
typedef pair<int,int> P;

int main() {
    int N,L;
    cin >> N >> L;
    vector<ll> vec(N);
    for(int i = 0;i < N;i++) {
        cin >> vec.at(i);
    }
    bool ret = false;
    int a = 0;
    for(int i = 0;i < N - 1;i++) {
        if(vec.at(i) + vec.at(i + 1) >= L) {
            ret = true;
            a = i + 1;
            break;
        }
    }
    if(ret == false) {
        cout << "Impossible" << endl;
    }
    else {
        cout << "Possible" << endl;
        vector<int> ret2;
        ret2.push_back(a);
        for(int i = a - 1;i >= 1;i--) {
            ret2.push_back(i);
        }
        for(int i = a + 1;i <= N - 1;i++) {
            ret2.push_back(i);
        }
        reverse(ret2.begin(),ret2.end());
        for(int i = 0;i < N - 1;i++) {
            cout << ret2.at(i) << endl;
        }
    }
}

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

int main() {
	int n,m,i,j,k,ans=0,b=1,cur,res,err,con,mod=1000000007;
	
	cin >> n;
	if(n==1){
		cout << 1; return 0;
	}
	vector<vector<int>> a(n, vector<int>(n,-1));
	for(i=0; i<n; i++){
		cin >> k;
		for(j=0; j<k; j++){
			cin >> cur >> res;
			a[i][cur-1]=res;
		}
	}
	
	/*
	for(i=0; i<n; i++){
		for(j=0; j<n; j++){
			cout << a[i][j] << ' ';
		}
		cout << endl;
	}
	*/
	
	b=1;
	for(i=0; i<n; i++){
		b*=2;
	}
	// cout << b;
	
	vector<int> jud(n);
	for(cur=0; cur<b; cur++){
		res=cur;
		err=0;
		for(i=0; i<n; i++){
			jud[i]=res%2;
			res/=2;
		}
		/*
		for(i=0; i<n; i++){
			cout << jud[i];
		}
		cout << endl;
		*/
		for(i=0; i<n; i++){
			if(jud[i]==1){
				for(j=0; j<n; j++){
					if((a[i][j]==1 && jud[j]==0) || a[i][j]==0 && jud[j]==1){
						err=1;
					}
				}
			}
		}
		if(err==0){
			con=0;
			for(i=0; i<n; i++){
				con+=jud[i];
			}
			ans=max(ans,con);
		}
	}
	cout << ans;
	

	
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;

int sum(int a, int b) {
    return a + b >= MOD ? a + b - MOD : a + b;
}
int sub(int a, int b) {
    return a - b < 0 ? a - b + MOD : a - b;
}
int mul(int a, int b) {
    return (1LL*a*b)%MOD;
}
int pw(int a, int b) {
	if (!b) return 1;
	int r = pw(a, b/2);
	r = mul(r, r);
	if (b%2) r = mul(r, a);
	return r;
}

const int MAXN = 2e5+7;
int p10[MAXN];

int getRange(int l, int r, int d) {
    int ans = p10[r];
    if (l > 0) ans = sub(ans, p10[l-1]);
    ans = mul(ans, d);
    return ans;
}

struct info {
    int l, r, c;
    info(int l, int r, int c) : l(l), r(r), c(c) { }
};

struct IntervalContainer {
    vector< int >color;
    map< int , int >mp;

    IntervalContainer(int n):color(n+1) {
        color[0] = 1;
        mp[0] = n-1;
        mp[n] = n;
    }

    /// will return the removed intervals in [l, r] with color
    vector<info>colorInterval(int l, int r, int c) {
        vector<info>rt;
        auto it = mp.lower_bound(l);

        if (l < it->first) {
            it--;
            color[l] = color[it->first];
            mp[l] = it->second;
            it->second = l-1;
            it++;
        }

        while (it->first <= r) {
            rt.emplace_back(it->first, min(r, it->second), color[it->first]);
            if (it->second > r) {
                color[r+1] = color[it->first];
                mp[r+1] = it->second;
            }
            it = mp.erase(it);
        }

        color[l] = c;
        mp[l] = r;
        return rt;
    }

    void print() {
        for (auto it : mp) {
            cout << it.first << " - " << it.second << " -> " << color[it.first]<<endl;
        }
    }
};

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

    p10[0] = 1;
    for (int i = 1; i < MAXN; i++) p10[i] = sum(mul(p10[i-1], 10), 1);

    int n, q;
    cin >> n >> q;

    int ans = getRange(0, n-1, 1);

    IntervalContainer ic(n);
    while (q--) {
        int l, r, d;
        cin >> l >> r >> d;
        l--; r--;
        l = n-1-l;
        r = n-1-r;
        swap(l, r);

        vector< info >vi = ic.colorInterval(l, r, d);
        for (info i : vi) {
            ans = sub(ans, getRange(i.l, i.r, i.c));
        }
        ans = sum(ans, getRange(l, r, d));

        cout << ans << "\n";
    }



    return 0;
}


Measured memory_bytes: 14340
#include <stdio.h>
#include <complex>
#include <vector>
#define PI 3.1415926535897932384626
#define MOD 200003

void FFT(std::vector< std::complex<long double> > &V, std::complex<long double> root, bool type)
{
	if(V.size()==1) return;
	
	//printf("%d?\n",V.size());
	std::vector< std::complex<long double> > V1,V2;
	for(int i=0;i<V.size();i+=2)
	{
		V1.push_back(V[i]);
		V2.push_back(V[i+1]);
	}
	std::complex<long double> newRoot = root*root;
	FFT(V1,newRoot,type);
	FFT(V2,newRoot,type);
	
	int n = V.size();
	std::complex<long double> p = 1;
	
	for(int i=0;i<n/2;i++)
	{
		V[i] = V1[i] + p*V2[i];
		p*=root;
	}
	for(int i=0;i<n/2;i++)
	{
		V[n/2+i] = V1[i] + p*V2[i];
		p*=root;
	}
	if(type)
	{
		for(int i=0;i<n;i++) V[i]/=2;
	}
}

int count[200010],position[200010];
long long int ans[600010];
std::vector< std::complex<long double> > V1,V2,V3;
int main()
{
	int p = 1;
	for(int i=0;i<MOD;i++)
	{
		position[p] = i;
		p*=2, p%=MOD;
	}
	long long int C = 0;
	int a;
	scanf("%d",&a);
	for(int i=1;i<=a;i++)
	{
		int b;
		scanf("%d",&b);
		if(b==0) continue;
		C += ((long long int)b*b)%MOD;
		count[position[b]]++;
	}
	int n = 524288;
	for(int i=0;i<MOD;i++) V1.push_back(count[i]);
	for(int i=MOD;i<n;i++) V1.push_back(0);
	std::complex<long double> root = std::exp(std::complex<long double>(0,(2*PI)/n));
	FFT(V1,root,false);
	for(int i=0;i<n;i++) V3.push_back(V1[i]*V1[i]);
	FFT(V3,std::complex<long double>(1,0)/root,true);
	for(int i=0;i<V3.size();i++) ans[i] = (long long int)((V3[i].real())+0.5);
	
	long long int sum = 0;
	long long int k = 1;
	for(int i=0;i<n;i++)
	{
		sum += k*ans[i];
		k*=2, k%=MOD;
	}
	printf("%lld",(sum-C)/2);
}

Measured memory_bytes: 69756
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define MOD 1000000007
#define MAX 100005
using Graph=vector<vector<int>>;

int main(){
  int A,B,C,X,Y;
  cin>>A>>B>>C>>X>>Y;
  int ans=A*X+B*Y;
  ans=min(ans,2*C*X+B*max(0,Y-X));
  ans=min(ans,2*C*Y+A*max(0,X-Y));
  cout<<ans<<endl;
}


Measured memory_bytes: 256
N = int(input())
ans = ''
for i in range(1, 99):
  if N <= 26 ** i:
    N -= 1
    for j in range(i):
      ans += chr(ord('a') + N % 26)
      N //= 26
    break
  else:
    N -= 26 ** i
print(ans[::-1])

Measured memory_bytes: 9188
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int H=sc.nextInt();
		int W=sc.nextInt();
		boolean conte=true;
		boolean[][] c=new boolean[H][W];
		int[][] field=new int[H][W];
		String[] str=new String[H];
		for(int i=0;i<H;i++){
			str[i]=sc.next();
			for(int k=0;k<W;k++){
				 field[i][k]=-1;
				 c[i][k]=false;
			 }
		}
		sc.close();
		for(int i=0;i<H;i++){
			int j=0;
			conte=true;
			 while(conte && j< str[i].length()){
				 if(str[i].indexOf('c',j) == -1){
					 conte=false; 
				 }else{
					 c[i][str[i].indexOf('c',j)]=true;
					 field[i][str[i].indexOf('c',j)]=0;
					 j=str[i].indexOf('c',j);
				 }
				 j++;
			 }
		}
		for(int i=0;i<H;i++){
			 for(int k=0;k<W-1;k++){
				 if(c[i][k]==true && c[i][k+1]==false){
					 field[i][k+1]=field[i][k]+1;
					 c[i][k+1]=true;
				 }
			 }	 
		}
		for(int i=0;i<H;i++){
			for (int k=0;k<W-1;k++){
				System.out.printf("%d ", field[i][k]);
			}
				System.out.printf("%d\n",field[i][W-1]);
		}
		
		
		
		
		
		
	}

}

Measured memory_bytes: 54236
#include <bits/stdc++.h>
using namespace std;
#define SELECTER(_1, _2, _3, SELECT, ...) SELECT
#define REP1(i, n) for(int (i)=0; (i)<(n); (i)++)
#define REP2(i, a, b) for(int (i)=(a); (i)<(b); (i)++)
#define REP(...) SELECTER(__VA_ARGS__, REP2, REP1,) (__VA_ARGS__)
#define MOD 1'000'000'007

template <class T> ostream& operator<<(ostream& os, const vector<T>& v){ os << "{"; for(size_t i=0; i<v.size(); i++) os << v[i] << (i+1==v.size() ? "" : ", "); os << "}"; return os; }
template <class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p){ return os << "{" << p.first << ", " << p.second << "}"; }

long long func(long long x){
    return x*x*x*x*x;
}

int main(){
    long long X;
    cin >> X;
    for(long long A=0; A<=1000; A++){
        for(long long B=-1000; B<=1000; B++){
            if(func(A)-func(B)==X){
                cout << A << " " << B << endl;
                return 0;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define SORT(a) sort(a.begin(), a.end())
#define RSORT(a) sort(a.rbegin(), a.rend())
#define REP(i, n) for (int i = 0; i < n; ++i)
#define RREP(i, n) for (int i = n; 0 <= i; --i)
#define FOR(i, start, end) for (int i = start; i < end; ++i)
#define RFOR(i, start, end) for (int i = start; end <= i; --i)
#define ALL(a) a.begin(), a.end()
#define MOD(a) a %= 1'000'000'007
#define INF32 1'050'000'000
#define INF64 4'000'000'000'000'000'000
using ll = long long;
using namespace std;
template <class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template <class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }

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

    int K; cin >> K;
    int S; cin >> S;
    int cnt = 0;
    REP (i, K+1) {
        FOR (j, i, K+1) {
            FOR (k, j, K+1) {
                if (i+j+k==S) {
                    if (i==j && j==k) cnt += 1;
                    else if (i==j || j==k) cnt += 3;
                    else cnt += 6;
                }
            }
        }
    }
    cout << cnt << '\n';
    return 0;
}




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

using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    string s;cin >> s;
    const int mod = 1e9 + 9;
    int res = 0;
    int hash = 0;int last = -1;
    for(int i = 0 ; i < (int)s.size() ; ++i){
        hash = (1ll * hash * 234 + s[i]) % mod;
        if(hash != last){
            last = hash;
            hash = 0;
            ++res;
        }
    }
    cout << res;
}

Measured memory_bytes: 720