akhauriyash/Code-Regression huggingface dataset:
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define v vector
#define ALL(x) x.begin(),x.end()
#define rALL(x) x.rbegin(),x.rend()
#define DEBUG

template<typename T> void DBG(const char* name, T&& H) {
	cerr << name << " = " << H << ')' << endl;
}

template<typename T, typename... Args> void DBG(const char* names, T&& H, Args&&... args) {
	const char* NEXT = strchr(names+1, ',');
	cerr.write(names, NEXT-names) << " = " << H << " |";
	DBG(NEXT+1, args...);
}

#ifdef DEBUG
	#define dbg(...) cerr << __FUNCTION__ << ' ' <<__LINE__ << " : (", DBG(#__VA_ARGS__, __VA_ARGS__)
#else
	#define dbg(...)
#endif

using ll = long long;
using ld = long double;

const long long mod = 1e9+7;
const long double PI = acos(-1.0);
const long long INF = 1e18;
const int maxN = 2e5+1;

struct SparseTable {
	using S = int;
	using T = long long;
	S n, k, m;
	vector<vector<vector<T>>> table;
	void init(S N, S M) {
		n = N;
		m = M;
		k = (S)(log2(n)) + 1;
		table.assign(k+1, vector<vector<T>> (m, vector<T>(n, 0)));
	}
	inline T func(T a, T b) {
		return max(a, b);
	}
	void build(vector<vector<T>> &arr) {
		for(int i = 0; i < n; i ++) {
			for(int j = 0; j < m; j ++) {
				table[0][j][i] = arr[j][i];
			}
		}
		for(S j = 1; j <= k; j ++) {
			for(S l = 0; l < m; l ++) {
				for(S i = 0; i + (1<<j) <= n; i ++) {
					table[j][l][i] = func(table[j-1][l][i], table[j-1][l][i + (1 << (j-1))]);
				}
			}
		}
	}
	T query(S left, S right) {
		S length = (right - left + 1);
		S K = (S)(log2(length));
		T ans = 0;
		for(int i = 0; i < m; i ++) {
			ans += func(table[K][i][left], table[K][i][right + 1 - (1 << K)]);
		}
		return ans;
	}
};

int N, M;
vector<long long> A(int(5e3), 0);
vector<vector<long long>> mat(200, vector<long long>(int(5e3)));
SparseTable st;

long long CostFunction(long long L, long long R) {
	long long happy = st.query(L, R);
	happy -= A[R] - A[L];
	return happy;
} 

long long DivideAndConquerDP(int L, int R, int optL, int optR) {
	if(L > R) return -1e18;
	int M = (L+R)/2, nextOpt = -1;
	long long best = -1e18;
	for(int i = max(M, optL); i <= optR; i ++) {
		long long val = CostFunction(M, i);
		if(val >= best) {
			best = val;
			nextOpt = i;
		}
	}
	best = max({best, DivideAndConquerDP(L, M-1, optL, nextOpt), DivideAndConquerDP(M+1, R, nextOpt, optR)});
	return best;
}

void Solve() {
	cin >> N >> M;
	for(int i = 1; i < N; i ++) {
		cin >> A[i];
		A[i] += A[i-1];
	}
	for(int i = 0; i < N; i ++) {
		for(int j = 0; j < M; j ++) {
			cin >> mat[j][i];
		}
	}
	st.init(N, M);
	st.build(mat);
	long long ans = DivideAndConquerDP(0, N-1, 0, N-1);
	cout << ans << endl;
}

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

	int tt = 1; 
	for(int i = 1; i <= tt; i ++) {
		Solve();
	}
	
	return 0;
}

Measured memory_bytes: 128724
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
from math import gcd

ans = 1
for i in range(N):
    t = int(input())
    g = gcd(ans, t)
    ans = ans*t//g

print(ans)

Measured memory_bytes: 62268
#include <bits/stdc++.h>
 
using namespace std;
#define ll long long
#define db long double
#define all(a) a.begin(),a.end()
#define pb push_back
#define f(i,l,u) for(ll i=l;i<u;i++)
#define lb lower_bound
#define ub upper_bound
#define pii pair<ll,ll> 
ll fac[1000001];
void powe(ll p)
{
     fac[0] = 1; 

     
    for (ll i = 1; i <= 1000000; i++) 
        fac[i] = (fac[i - 1] *i) % p; 
  
}
 
 
        
      long long power( long long x, 
                         ll y, ll p) 
{ 
   long long res = 1; // Initialize result 
  
    x = x % p; 
    while (y > 0) { 
        // If y is odd, multiply x with result 
        if (y & 1) 
            res = (res * x) % p; 
  
        // y must be even now 
        y = y >> 1; // y = y/2 
        x = (x * x) % p; 
    } 
    return res; 
} 
  
// Returns n^(-1) mod p 
 long long modInverse( long long n, ll p) 
{ 
    return power(n, p - 2, p); 
} 
  
// Returns nCr % p using Fermat's little 
// theorem. 
 long long nCrModPFermat( long long n, 
                                 ll r, ll p) 
{ 
    // Base case 
    if (r == 0) 
        return 1; 
  
       return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p; 
} 
 ll gcd(ll a,ll b)
 {
     if(b==0)
     return a;
     return gcd(b,a%b);
 }
  
int main() {
   ll t=1;

  // cin>>t;
  powe(1000000007);
  
   //ll vis[10]={0};
   while(t--)
   {
   
    ll n;
    cin>>n;
    ll ggg=360;
  cout<<ggg/gcd(n,ggg);
   }
  
   

      

return 0;    
}

Measured memory_bytes: 11440
#include <bits/stdc++.h>
using namespace std;
#define endl			"\n"
#define ll				long long
#define all(v)			((v).begin()), ((v).end())
#define sz(v)			((int)((v).size()))
#define clr(v, d)		memset(v, d, sizeof(v))
#define rep(i, v)		for(int i=0;i<sz(v);++i)
#define lp(i, n)		for(int i=0;i<(int)(n);++i)
#define lpi(i, j, n)	for(int i=(j);i<(int)(n);++i)
#define lpd(i, j, n)	for(int i=(j);i>=(int)(n);--i)
#define vi				vector <int>
#define vl				vector <ll>
#define ii				pair <ll,ll>
#define vii				vector <ii>
#define ull				unsigned long long
const double PI = 2 * acos(0.0);
void run() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
}
void solve() {
	ll L;
	cin >> L;
	long double t = 1.0 * (L) / 3.0;
	cout << fixed << setprecision(9) << t * t * t << endl;

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


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

void trace(int A[], int n) {
	for (int i = 0; i < n; i++) {
		if (i) cout << " ";
		cout << A[i];
	}
	cout << endl;
}

int bubblesort(int A[], int n) {
	bool flag = true;
	int cnt = 0;
	for (int i = 0; flag; i++) {
		flag = false;
		for (int j = n - 1; j >= i + 1; j--) {
			if (A[j] < A[j - 1]) {
				swap(A[j], A[j - 1]);
				flag = true;
				cnt++;
			}
		}
	}
	return cnt;
}

int main() {
	int n; cin >> n;
	int A[110];
	for (int i = 0; i < n; i++) cin >> A[i];
	int ans = bubblesort(A, n);
	trace(A, n);
	cout << ans << endl;
	return 0;
}


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

int main(){
        int h, w;
        scanf("%d %d", &h, &w);
        int wei[h][w], bai[h][w];
        for(int i=0; i<h; i++) for(int j=0; j<w; j++) scanf("%d", &wei[i][j]);

        int mn = 1e8;
        for(int i=0; i<h; i++){
                for(int j=0; j<w; j++){

                        for(int k=0; k<h; k++) for(int l=0; l<w; l++) bai[k][l]=1e8;
                        for(int k=0; k<h; k++) for(int l=0; l<w; l++) bai[k][l]=min(bai[k][l], abs(k-i));
                        for(int k=0; k<h; k++) for(int l=0; l<w; l++) bai[k][l]=min(bai[k][l], abs(l-j));

                        int sm = 0;
                        for(int k=0; k<h; k++){
                                for(int l=0; l<w; l++){
                                        sm += wei[k][l] * bai[k][l];
                                }
                        }
                        mn = min(mn, sm);
                }
        }
        printf("%d\n", mn);
        return 0;
}


Measured memory_bytes: 3212
#include <stdio.h>

int main(void) {
  int x[5];
  for (int i=0;i<5;++i) {
    scanf("%d\n",x+i);
    if (x[i]==0) {
      printf("%d\n",i+1);
      break;
    }
  }
  return 0;
}


Measured memory_bytes: 1724
for i in range(3) :
    h_s, m_s, s_s, h_e, m_e, s_e = map(int, input().split())
    x = h_e * 3600 + m_e * 60 + s_e - h_s * 3600 - m_s * 60 - s_s
    h_a = x // 3600
    m_a = x % 3600 // 60
    s_a = x % 3600 % 60
    print(h_a, m_a, s_a)


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

typedef long long ll;
//loop
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//STL
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))

//const
#define MOD 1000000007 //10^9+7:合同式の法

//acronym
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

void Main() {
    int n;
    cin >> n;

    string ans = "No";
    REP(i,3) {
        if (n % 10 == 7) {
            ans = "Yes";
            break;
        }
        n /= 10;
    }
    
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Main();
    return 0;
}


Measured memory_bytes: 3632
<?php
list($a, $b) = explode(' ', trim(fgets(STDIN)));
list($aNum, $bNum) = explode(' ', trim(fgets(STDIN)));
$discard = trim(fgets(STDIN));

if ($a === $discard) {
  --$aNum;
} elseif ($b === $discard) {
  --$bNum;
}
echo $aNum, ' ', $bNum;

Measured memory_bytes: 4728
#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int N = 64;
vector<int> G[N];
int n, m;
set<pair<int, int>> mp;

int dfs_clock, top, ins[N], stk[N], dfn[N], low[N];

void tarjan(int u, int pre) {
    dfn[u] = low[u] = ++dfs_clock;
    ins[u] = true;
    stk[top++] = u;

    for(auto v : G[u]) if(v != pre) {
        if(dfn[v] == 0) {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if(low[v] > dfn[u]) mp.insert(make_pair(min(u, v), max(u, v)));
        } else if(ins[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }

    if(dfn[u] == low[u]) {
        int v;
        do {
            ins[v = stk[--top]] = false;
        } while(v != u);
    }
}

int fuck() {

    for(int i = 1; i <= n; ++i) {
        if(dfn[i] == 0) tarjan(i, i);
    }

    return mp.size();
}

int main(int argc, char **argv) {
    cin >> n >> m;
    while(m--) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    cout << fuck() << endl;
    return 0;
}


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

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 100010;
const double eps = 1e-6;

int n, k;
int a[N], d[N];

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

    cout << (n + k - 3) / (k - 1) << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<cmath>
using namespace std;
#define REP(i, limit) for(int i=0; i< limit; ++i)
#define FOR(i, j, limit) for(int i=j; i< limit; ++i)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define LL long long
int INF = 2147483647;
LL LINF = 9223372036854775807;
LL MOD = 1000000007;
typedef pair<int, int>P;
typedef pair<LL, LL>PL;
typedef vector<int> vi;
typedef vector<LL> vl;


int main(){
  int N;
  cin>>N;
  if(N==7||N==5||N==3)cout<<"YES"<<endl;
  else cout<<"NO"<<endl;


  return 0;
}


Measured memory_bytes: 764
import java.util.Scanner;

public class Main {
    static int N;
    static int K;
    static int[] x;

    private static void init() {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        K = scanner.nextInt();
        x = new int[N];
        for(int i = 0; i < N; i++) {
            x[i] = scanner.nextInt();
        }
        scanner.close();
    }


    public static void main(String args[]) {
        init();

        int ans = Integer.MAX_VALUE;
        for(int i = 0; i < N - K + 1; i++) {
            int left = Math.abs(x[i]) + Math.abs(x[i + K - 1] - x[i]);
            int right = Math.abs((x[i + K - 1])) + Math.abs(x[i + K - 1] - x[i]);
            int cur = Math.min(left, right);
            ans = Math.min(ans, cur);
        }
        System.out.println(ans);

    }
}

Measured memory_bytes: 49228
import math
n = int(input())
A = list(map(int,input().split()))

L = 2
R = 2
k = 0
for i in range(n):
    if L//A[n-1-i] == R//A[n-1-i] and L % A[n-1-i] != 0:
        k = 1
        break
    else:
        L = (math.ceil(L/A[n-1-i]))*A[n-1-i]
        R = (R//A[n-1-i]+1) * A[n-1-i] - 1
print(L,R) if k == 0 else print("-1")

Measured memory_bytes: 15020
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
int main()
{
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  lli x = max(a, b);
  lli y = min(a, b);
  
  lli m = max(c, d);
  lli n = min(c, d);
  
  cout << max(x*m, max(x*n, max(y*m, y*n))) << endl;
}

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

int main()
{
	int n;
	cin >> n;
	std::vector<long> a(n + 2);
	std::vector<long> b(n + 1);
	long sum = 0;
	for (int i = 1; i <= n + 1; ++i)
	{
		cin >> a[i];
	}
	for (int i = 1; i <= n; ++i)
	{
		cin >> b[i];
	}
	for (int i = 1; i <= n; ++i)
	{
		//モンスターの数が倒した数より大きければ
		if (a[i] >= b[i])
		{
			sum += b[i];
			
		}
		else
		{
			sum += a[i];
			b[i] = b[i] - a[i];//残り倒せる数
			if (a[i + 1] >= b[i])
			{
				sum += b[i];
				a[i + 1] = a[i + 1] - b[i];

			}
			else
			{
				sum += a[i + 1];
				a[i + 1] = 0;
			}
		}

	}
	cout << sum << endl;
}

Measured memory_bytes: 1792
import java.util.HashMap;
import java.util.Scanner;

public class Main {
	
	
	
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		if(n%1000==0) {
			System.out.println(0);
		}
		else {
			System.out.println(((n/1000)+1)*1000-n);
		}
	}

}


Measured memory_bytes: 35628
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
#define EPS (1e-10)
#define equals(a, b) (fabs((a) - (b)) < EPS)

class Point {
public:
    double x, y;

    Point(double x = 0.0, double y = 0.0): x(x), y(y) {};

    Point operator + (Point &p) {return Point(x + p.x, y + p.y);}
    Point operator - (Point &p) {return Point(x - p.x, y - p.y);}
    Point operator * (double k) {return Point(x * k, y * k);}
    Point operator / (double k) {return Point(x / k, y / k);}

    double norm(void) {return x * x + y * y;}
    double abs(void) {return sqrt(norm());}

    bool operator == (const Point &p) const {
        return fabs(x - p.x) < EPS && fabs(y - p.y) < EPS;
    }

    bool operator < (const Point &p) const {
        return x != p.x ? x < p.x : y < p.y;
    }

    double dot(Point a) {
        return x * a.x + y * a.y;
    }

    double cross(Point a) {
        return x * a.y - y * a.x;
    }
};

typedef Point Vector;

struct Segment {
    Point p1, p2;
};


static const int COUNTER_CLOCKWISE = 1;
static const int CLOCKWISE = -1;
static const int ONLINE_BACK = 2;
static const int ONLINE_FRONT = -2;
static const int ON_SEGMENT = 0;

int ccw(Point p0, Point p1, Point p2) {
    Vector a = p1 - p0;
    Vector b = p2 - p0;
    if (a.cross(b) > EPS) return COUNTER_CLOCKWISE;
    if (a.cross(b) < -EPS) return CLOCKWISE;
    if (a.dot(b) < -EPS) return ONLINE_BACK;
    if (a.norm() < b.norm()) return ONLINE_FRONT;
    return ON_SEGMENT;
}


int main(void) {
    int x1, x2, y1, y2, q, px, py;
    scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
    Point p0 = Point(x1, y1);
    Point p1 = Point(x2, y2);
    scanf("%d", &q);

    for (int i = 0; i < q; i++) {
        scanf("%d %d", &px, &py);
        int ret = ccw(p0, p1, Point(px, py));

        switch (ret) {
            case -2: printf("ONLINE_FRONT\n"); break;
            case -1: printf("CLOCKWISE\n"); break;
            case 0:  printf("ON_SEGMENT\n"); break;
            case 1:  printf("COUNTER_CLOCKWISE\n"); break;
            case 2:  printf("ONLINE_BACK\n"); break;
        }
    }

    return 0;
}

Measured memory_bytes: 1012
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
typedef long long ll;
#define _GLIBCXX_DEBUG
typedef vector<int> vec;
typedef vector<ll> lvec;
typedef vector<char> cvec;
typedef vector<double> dvec;
typedef pair<ll, ll> LP;
typedef tuple<ll, ll, ll> LT;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
#define fs first
#define sc second
int main()	{
  int n;
  cin>>n;
  vector<int>p(n);
  rep(i,n) cin>>p[i];
  int sav=2000001;
  int cnt=0;
  rep(i,n){
    if(sav>=p[i]){
      cnt++;
    }
    sav=min(sav,p[i]);
  }
  cout<<cnt<<endl;
}

Measured memory_bytes: 1024
X, N = map(int, input().split())

if N == 0:
    print(X)
    exit()

P = list(map(int, input().split()))

for i in range(100):
    left = X - i
    right = X + i
    
    if left not in P and right not in P:
        print(min(left, right))
        exit()
    elif left not in P and right in P:
        print(left)
        exit()
    elif left in P and right not in P:
        print(right)
        exit()
    else:
        continue


Measured memory_bytes: 9200
using System;

namespace C
{
    class Program
    {
        static void Main(string[] args)
        {
            var ABHM = Array.ConvertAll(Console.ReadLine().Split(' '), double.Parse);
            var A = ABHM[0]; var B = ABHM[1]; var H = ABHM[2]; var M = ABHM[3];
            var minute = 60 * H + M;
            var Hangle = 360 * minute / 720;
            var Mangle = 360 * M / 60;
            Console.WriteLine(Math.Sqrt(A * A + B * B - 2 * A * B * Math.Cos(Math.Abs(Hangle - Mangle) * Math.PI / 180)));
        }
    }
}


Measured memory_bytes: 27956
#include<cstdio>
#include<utility>
#include<queue>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
typedef pair<string,int> psi;

int main(){
    queue<psi> all;
    int n, q;
    scanf("%d%d", &n, &q);
    psi pp;
    for(int i = 0; i < n; i++){
        cin >>pp.first >> pp.second;
        all.push(pp);
    }
    int t=0;
    while(!all.empty()){
        pp = all.front();
        all.pop();
        if(pp.second <= q){
            t += pp.second;
            cout << pp.first <<" " << t<< endl;
        }
        else {
            pp.second -= q;
            all.push(pp);
            t += q;
        }
    }
    return 0;
}



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

using namespace std;

#define FOR(a,b,c) for(int a=b, __c=c; a<=__c; ++a)
#define FORD(a,b,c) for(int a=b, __c=c; a>=__c; --a)
#define forv(a,b) for(auto &a:b)

#define ii pair<int,int>
#define fi first
#define se second
#define all(a) begin(a),end(a)
#define reset(f,x) memset(f,x,sizeof(f))
#define pb push_back
#define eb emplace_back
#define fasty ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)

#define bit(x,i) (x>>(i-1)&1ll)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1ll<<(i-1)))

const int N=2e5+5;
int n;
ii p[N];

int32_t main(){
   fasty;

   #define task "point"
   if(fopen(task".in", "r")) freopen(task".in", "r", stdin);

   cin>>n;
   FOR(i,1,n) cin>>p[i].fi>>p[i].se;

   vector<int> x,y;
   FOR(i,1,n){
      x.pb(p[i].fi-p[i].se);
      y.pb(p[i].fi+p[i].se);
   }
   sort(all(x)); sort(all(y));
   cout<<max(x.back()-x[0], y.back()-y[0]);
}


Measured memory_bytes: 6656
class Combination:                                      # 計算量は O(n_max + log(mod))
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):                     # 階乗(= n_max !)の逆元を生成
            f = f * i % mod                             # 動的計画法による階乗の高速計算
            fac.append(f)                               # fac は階乗のリスト
        f = pow(f, mod-2, mod)                          # 階乗から階乗の逆元を計算。フェルマーの小定理より、　a^-1 = a^(p-2) (mod p) if p = prime number and p and a are coprime
                                                        # python の pow 関数は自動的に mod の下での高速累乗を行ってくれる
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):                   # 上記の階乗の逆元から階乗の逆元のリストを生成（＝ facinv ）
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    def H(self, n, r):                                  # (箱区別:〇　ボール区別:×　空箱:〇)　重複組み合わせ nHm
        if (n == 0 and r > 0) or r < 0: return 0
        return self.fac[n+r-1] * self.facinv[r] % self.mod * self.facinv[n-1] % self.mod

N, M, K = map(int, input().split())
MOD=998244353
C = Combination(N,MOD)
res = 0
for k in range(K+1):
    res += C.H(N - k,k) * M * pow(M - 1, N - k - 1, MOD)
    res %= MOD
print(res)

Measured memory_bytes: 104000
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Math;

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            A();
        }

        static void A()
        {
            var S = Read();
            var before = string.Empty;
            var ans = 0;
            foreach (var s in S)
            {
                if (before == "S" && s == 'R')
                {
                    ans = 1;
                }
                else if (s == 'R') ans++;
                before = s.ToString();
            }

            Println(ans);
        }

        static List<long> ReadLines(long n)
        {
            var l = new List<long>();
            for (long i = 0; i < n; i++)
            {
                l.Add(ReadLong());
            }
            return l;
        }

        static void YESOrNO(bool e) => Println(e ? "YES" : "NO");
        static void YesOrNo(bool e) => Println(e ? "Yes" : "No");

        static IEnumerable<int> Range(int start, int stop)
        {
            if (start < 0 || stop < 0 || start > stop || (start <= 0 && stop <= 0))
                return new List<int>();

            return Enumerable.Range(start, stop - start);
        }

        static bool IsDigit(string str)
        {
            var i = 0;
            return int.TryParse(str, out i);
        }

        static int SumDigits(long num)
        {
            return num.ToString().Select(x => x.ToString()).Sum(int.Parse);
        }

        static int[] ToIntArray(string str)
        {
            return str.Select(x => x.ToString()).Select(int.Parse).ToArray();
        }

        static long Gcd(long a, long b) => b == 0 ? a : Gcd(b, a % b);
        static long Lcm(long a, long b) => a / Gcd(a, b) * b;

        static bool IsPrime(int x)
        {
            if (x <= 1 || (x != 2 && x % 2 == 0)) return false;
            if (x == 2) return true;

            for (int i = 3; i < x; i += 2)
                if (x % i == 0) return false;

            return true;
        }

        static string Read() => Console.ReadLine();
        static int ReadInt() => int.Parse(Read());
        static long ReadLong() => long.Parse(Read());

        static List<string> ReadSplit() => Read().Split().ToList();
        static List<int> ReadSplitInt() => Read().Split().Select(int.Parse).ToList();
        static List<long> ReadSplitLong() => Read().Split().Select(long.Parse).ToList();

        static void Print(object value) => Console.Write(value.ToString());
        static void Println(object value) => Console.WriteLine(value.ToString());
        static string Join<T>(IEnumerable<T> list) => string.Join("", list);
    }

    public static class MyExtensions
    {
        public static string Slice(this string str, int start = 0, int stop = 0)
        {
            if (start > str.Length || stop > str.Length || start < 0 || stop < 0)
                return "";

            if (stop == 0) stop = str.Length;
            return str.Substring(start, stop - start);
        }
    }
}



Measured memory_bytes: 25948
N = int(input())
X = list(map(int, (input().split())))

distance = lambda Xi, P: (Xi - P) ** 2
all_distance = lambda X, P: sum([distance(Xi, P) for Xi in X])

X_min = min(X)
X_max = max(X)

answer = None
for P in range(X_min, X_max + 1):
    total = all_distance(X, P)
    answer = min(total, answer) if answer is not None else total

print(answer)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)

int main(){
    ll n;
    string s;
    cin >> n >> s;
    vector<string> v;
    for(char i = '0'; i <= '9'; i++) {
        for(char j = '0'; j <= '9'; j++) {
            for(char k = '0'; k <= '9'; k++) {
                string tmp(3, 0);
                tmp[0] = i; tmp[1] = j; tmp[2] = k;
                v.push_back(tmp);
            }
        }
    }
    ll ans = 0;
    for(auto e : v) {
        ll itr = 0;
        bool f = false;
        rep(i, 0, n) {
            if(s[i] == e[itr]) itr++;
            if(itr == 3) {
                f = true;
                break;
            }
        }
        if(f) ans++;
    }
    cout << ans << endl;
    return 0;
}

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

const int N = 1e5;
struct SEG {
  ll data[ N  * 4];
  int n;
  SEG(int t){
    n = 1;
    while(n<t)n<<=1;
  }
  ll get(int i){ 
    return data[i+=n-1];
  }
  void set(int i, ll x){ 
    data[i+=n-1]=x;
    while(i>0)i=(i-1)/2,data[i]=data[i*2+1]+data[i*2+2];
  }
  ll query(int a, int b, int k = 0, int l=0, int r=-1){
    if(r<0)r=n;
    if(b <= l || r <= a) return 0;
    if(a <= l && r <= b) return data[k];
    return
      query(a, b, k * 2+1,l,(l+r)>>1)+
      query(a, b, k * 2+2,(l+r)>>1,r);
  }
};

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  int n, q;
  cin >> n;
  cin >> q;
  SEG seg(N);
  for(int i = 0; i < q; i++) {
    int com, x, y;
    cin >> com >> x >> y;
    if(com == 0) {
      x--;
      seg.set(x, seg.get(x) + y);
    } else {
      cout << seg.query(x-1, y) << endl;
    }
  }
  return 0;
}



Measured memory_bytes: 4728
n=int(input())
s=input()

remain = [[0,0,0]]
for i in range(n):
    r, g, b = remain[-1]
    if s[-i-1] == "R":
        r = r+1
    elif s[-i-1] == "G":
        g = g + 1
    elif s[-i-1] == "B":
        b = b + 1

    remain.append([r,g,b])

total = 0

rgb="RGB"
for i in range(n-2):
    first = s[i]
    search = []
    for j in range(3):
        if j==rgb.find(first):
            continue
        else:
            search.append(j)
    total = total + (remain[-i-2][search[0]]*remain[-i-2][search[1]])
    try:
        for j in range(1,n):
            if s[i] != s[i+j] and s[i] != s[i+j+j] and s[i+j] != s[i+j+j]:
                total -= 1
    except:
        pass


print(total)

Measured memory_bytes: 9288
#include <iostream>
#include <iomanip>
using namespace std;
int main(){
  int a, b, d ,r;
  double f;
  cin >> a >> b;
  d = a / b;
  r = a % b;
  f = (double)a / (double)b;
  cout << d << " " << r << " " << fixed << f << endl;



  return 0;
}

Measured memory_bytes: 1244
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstdio>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
using namespace std;
#define MOD 1000000007
#define endl "\n" 
#define rep(i,n) for(int i = 0; i < (n); ++i)
typedef long long ll;

ll cnt;
int n;
int A[1000000];
vector<int> G;

void insert_sort(int a[], int n, int g) {
    for(int i = g; i < n; ++i) {
        int v = a[i];
        int j = i-g;
        while(j >= 0 && a[j] > v) {
            a[j+g] = a[j];
            j -= g;
            ++cnt;
        }
        a[j+g] = v;
    } 
}

void shell_sort(int a[], int n) {
    for(int h = 1; ; ) {
        if(h > n) break;
        G.push_back(h);
        h = 3*h + 1;
    }    

    for(int i = G.size()-1; i >= 0; --i) {
        insert_sort(A, n, G[i]);
    }
}

int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
  
    cin >> n;
    rep(i,n) cin >> A[i];
    cnt = 0;

    shell_sort(A,n);

    printf("%lld\n", G.size());
    for(int i=G.size()-1; i >= 0; --i) {
        printf("%d", G[i]);
        if(i) printf(" ");
    }
    printf("\n");
    printf("%lld\n", cnt);
    for(int i = 0; i < n; ++i) {
        printf("%d\n", A[i]);
    }

    return 0;
}



Measured memory_bytes: 7196
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] count = new int[N];
		for (int i = 0; i < N-1; i++) {
			count[sc.nextInt()-1]++;
		}
		for (int i : count) {
			System.out.println(i);
		}
	}
}

Measured memory_bytes: 60876
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
  int a,b;
  cin>>a>>b;
  if(a<b){
    cout<<"a < b"<<'\n';
  }
  if(a>b){
    cout<<"a > b"<<'\n';
  }
  if(a==b){
    cout<<"a == b"<<'\n';
  }
  return(0);
}



Measured memory_bytes: 3056
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long ll;
const ll INF = 1e+12 + 1;

int n;
ll k;
vector<ll> a, f;

bool C(ll x){
    ll res = 0;
    for(int i = 0; i < n; ++i){
        ll tx = a[i], ty = f[i];
        if(tx * ty > x){
            res += (ll)ceil((double)(tx * ty - x) / ty);
        }
    }

    return res <= k;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> k;
    for(int i = 0; i < n; ++i){
        int tmp;
        cin >> tmp;
        a.push_back(tmp);
    }
    for(int i = 0; i < n; ++i){
        int tmp;
        cin >> tmp;
        f.push_back(tmp);
    }
    sort(a.begin(), a.end());
    sort(f.begin(), f.end(), greater<ll>());
    
    ll lb = -1, ub = INF;
    while(ub - lb > 1){
        ll mid = (ub + lb) / 2;
        if(C(mid))  ub = mid;
        else        lb = mid;
    }
    cout << ub << endl;
}

Measured memory_bytes: 4848
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <functional>
#include <string>
#include <queue>
#include <cstdint>
using namespace std;

#define rep(i,a,b) for(long long int i=a; i<b; i++ )
#define REP(i,n) rep(i,0,n)


long long int combination( int n,  int r) {
  if(n==0 || n==1) {return 0;}

  if ( r * 2 > n ) r = n - r;
  long long int dividend = 1;
  long long int divisor  = 1;
  for ( int i = 1; i <= r; ++i ) {
    dividend *= (n-i+1);
    divisor  *= i;
  }
  return dividend / divisor;
}

int main()
{
  int N; cin >> N;
  vector<int> a(N); 
  REP(i,N){ cin >> a[i]; }
  vector<int> count(N+1);

  REP(i,N){ 
    count[ a[i]-1 ] += 1; 
  }

  long long int sum = 0;

  REP(i,N){
    sum += combination( count[i], 2 );
  }


  REP(i, N){
    cout << sum - combination( count[a[i]-1], 2 ) + combination( count[a[i]-1]-1, 2 ) << endl;
  }

  return 0;
}

Measured memory_bytes: 4096
import sys
import copy
from collections import deque
stdin = sys.stdin

mod = 10**9+7

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, k = na()
a = na()

def calc_lux(a):
    imosu = [0 for _ in range(len(a))]
    res = [0 for _ in range(len(a))]
    cnt = 0
    for i in range(len(a)):
        light = a[i]
        le = max(0, i-light)
        imosu[le] += 1
        if i+light < n-1:
            imosu[i+light+1] -= 1

    tmp = 0
    for i in range(len(res)):
        tmp += imosu[i]
        res[i] += tmp
    return res

for _ in range(k):
    # calc lux from a
    lux = calc_lux(a)

    if a==lux:
        a = lux
        break

    # overwrite a
    a = lux
    # print(lux)

print(" ".join([str(i) for i in a]))

Measured memory_bytes: 182252
#include <iostream>
using namespace std;
int main(void){
  int D, N;
  cin >> D >> N;
  int a = 1;
  for(int i=0; i<D; i++){
    a *= 100;
  }
  int present = 0;
  for(int i = 1; i <= N; i++){
    present++;
    if(0 == (i % 100)){
      present++;
      
    }    
  }
  present *= a;
  cout << present << endl;
  return 0;
}

Measured memory_bytes: 256
import std.stdio, std.string, std.conv;
import std.range, std.algorithm, std.array;


void main() {
    int a, b, c, d;
    scan(a, b, c, d);
    writeln(max(a*b, c*d));
}



void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}



void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}


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

int main(void)
{
	int a, b;
	cin >> a >> b;
	if(a == b)		cout << "a == b" << endl;
	else if(a > b)	cout << "a > b" << endl;
	else			cout << "a < b" << endl;

	return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <set>

using namespace std;

int main(int argc, char const* argv[])
{
	int n;
	cin >> n;
	set<int> st;
	for(int i = 0; i < n; i++){
			int d;
			cin >> d;
			st.insert(d);
	}
	cout << st.size() << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,N) for(int i = 0; i < (N); i++)
#define erep(i,N) for(int i = N; i >= 0; i--)
const ll INF = 1000000000000000000;
//input



//processing



//dpTable
//int dp[100050];

int main(){
    char c;
    cin >> c;
    if ('A' <= c && c <= 'Z') cout << 'A' << endl;
    else cout << 'a' << endl;
    return 0;
}


Measured memory_bytes: 3632
<?php
fscanf(STDIN, '%d %d', $n, $m);
for ($i  = 0; $i < $m; $i++) {
    fscanf(STDIN, '%d %d', $_p, $y[]);
    $p[] = $_p - 1;
    $c[] = $i;
}
array_multisort($p, $y, $c);
$j = 1;
for($i = 0; $i < $m; $i++) {
    if (($p[$i - 1] ?? $p[$i]) !== $p[$i]) $j = 1;
    $num[$c[$i]] = str_pad($p[$i] + 1, 6, 0, STR_PAD_LEFT) . str_pad($j, 6, 0, STR_PAD_LEFT);
    $j++;
}
for($i = 0; $i < $m; $i++) echo $num[$i] . PHP_EOL;

Measured memory_bytes: 39792
#pragma GCC optimize("O3")
//#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")
#define io_init cin.tie(0);ios::sync_with_stdio(0);cout<<setprecision(10)
#include <bits/stdc++.h>
constexpr int INF = 2147483647;
constexpr long long int INF_LL = 9223372036854775807;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;


//x1*y2 - x2*y1 = S
//x1 = 1e9, y2 = 1e9
//x2 = 1    y1 = ?
int main() {
    io_init;
    ll S;
    cin >> S;
    if (S == 1e18) {
        cout << 0 << " " << 0 << " " << 1e9 << " " << 0 << " " << 1e9 << " " << 1e9 << endl;
        return 0;
    }
    ll x1, x2, y1, y2;
    x1 = 1e9;
    x2 = 1;
    y2 = (S+1e9 - 1) / 1e9;
    y1 = x1 * y2 - S;
    //cout << x1 * y2 - x2 * y1 << endl;
    cout << 0 << " " << 0 << " " << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
}


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

signed main(){
	long long a, b, c, d;
	scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
	printf("%lld\n", max({a * c, a * d, b * c, b * d}));
	return 0;
}

Measured memory_bytes: 3804
s = list(input())
k = int(input())
if '1' not in s:
    print(s[0])
else:
    num = 0
    for i in range(len(s)):
        if s[0] == "1":
            s.pop(0)
            num += 1
        else:
            break
    if num >= k:
        print(1)
    else:
        print(s[0])


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int (i)=0;i<(n);i++)
#define REP(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define INF LLONG_MAX - 100
#define MOD 1000000007
#define fcout cout << fixed << setprecision(15)
#define int long long
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)?"YES":"NO")
#define lowb lower_bound
#define upb upper_bound
typedef long long ll;
typedef pair<int, int> P;
typedef priority_queue<int> pque;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int lcm(int a,int b){return a/gcd(a,b)*b;};
int mod(int a,int b){return (a+b-1)/b;};
int month[12] = {31,28,31,30,31,30,31,31,30,31,30,31};
template<typename A, size_t N, typename T>
void Fill(A(&array)[N],const T &val){std::fill((T*)array,(T*)(array+N),val);}
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;};



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

	int n, m;
	cin >> n >> m;
	int p[m];
	string s[m];
	rep(i, m) {
		cin >> p[i] >> s[i];
		p[i]--;
	}

	int pe[100010], ac[100010];
	Fill(pe, 0);
	Fill(ac, 0);
	rep(i, m) {
		if(s[i] == "AC") {
			ac[p[i]] = 1;
		} else {
			if(!ac[p[i]]) pe[p[i]]++;
		}
	}
	int ans1 = 0, ans2 = 0;
	rep(i, n) {
		if(ac[i] == 1) {
			ans1++;
			ans2 += pe[i];
		}
	}
	cout << ans1 << " " << ans2 << endl;
	// rep(i, n) {
	// 	cout << ac[i] << " " << pe[i] << endl;
	// }
	return 0;
}

Measured memory_bytes: 8064
local N = io.read("n")
local V = {} for i=1,N do V[i] = io.read("n") end
local C = {} for i=1,N do C[i] = io.read("n") end
local ans = 0
for i=1,N do
    local diff = V[i] - C[i]
    if diff > 0 then
        ans = ans + diff
    end
end
print(ans)


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


int main()
{
    int N;
    
    long K;
    cin >> N >> K;
    
    vector<pair<int,int>> data;
    
    for(int i = 0;i<N;i++)
    {
        int a, b;
        cin >> a >> b;
        pair<int,int> p = {a,b};
        data.push_back(p);
    }
    
    sort(data.begin(),data.end());
    long count = 0;
    
    for(int i = 0;i<N;i++)
    {
        count += data[i].second;
        if(count >= K)
        {
            cout << data[i].first << endl;
            break;
        }
    }
    

 
    return 0;
    
}

Measured memory_bytes: 1400
import java.util.*;
	import java.util.Map.Entry;
	 
	 
	 class Main {
		 static int mod =  (int) (Math.pow(10,9)+7);
//		 static int mod =  (int) 998244353;
		 static List<ArrayList<Integer>> list= new ArrayList<ArrayList<Integer>>();
		 public static void main(String[] args) {
	    	
	        Scanner sc = new Scanner(System.in);

	        int N = sc.nextInt();	
	        long[] a = new long[N];
	        for (int i=0 ; i<N; i++) {
	            a[i] = Long.parseLong(sc.next());
	        }
	        long ans =0;
	        long pre =-1;
	        for(int i=0;i<N;i++) {
	        	if(a[i]>pre+1) {
	        		System.out.println(-1);
	        		return;
	        	} else if(a[i]==pre+1){
	        		ans++;
	        	} else {
	        		ans=ans+a[i];
	        	}
	        	pre=a[i];
	        }
	        
	        
	        System.out.print(ans-1);
		 }
	}

Measured memory_bytes: 63432
#include <stdio.h>
#include <math.h>

int n;

int main() {
  scanf("%d", &n);
  double a[3][n];
  double score[3][n + 1];
  for (size_t i = 0; i < n; i++) {
    scanf("%lf%lf%lf", &a[0][i], &a[1][i], &a[2][i]);
  }
  for (size_t i = 0; i < n; i++) {
    for (size_t j = 0; j < 3; j++) {
      score[j][i] = 0;
    }
  }
  for (size_t i = 0; i < n; i++) {
    score[0][i + 1] = fmax(score[1][i],score[2][i]) + a[0][i];
    score[1][i + 1] = fmax(score[0][i],score[2][i]) + a[1][i];
    score[2][i + 1] = fmax(score[1][i],score[0][i]) + a[2][i];
  }
  printf("%d\n", (int)fmax(score[0][n], fmax(score[1][n], score[2][n])));
  return 0;
}


Measured memory_bytes: 4864
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 9999999

using namespace std;

typedef pair<int, int> P;

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

int a[200001];
int b[200001];
int main() {
	int N, K;
	set<int>s;
	cin >> N >> K;
	REP(i, N) {
		cin >> a[i];
		s.insert(a[i]);
	}
	int c = s.size();
	SORT(a, N);
	b[0] = 1;
	int j = 0;
	for (int i=1; i < N;i++) {
		if (a[i] != a[i - 1]) {
			j++;
		}
		b[j]++;
	}
	SORT(b, c);
	int ans = 0;
	if (c <= K) {
		cout << 0 << endl;
		return 0;
	}
	int d = c - K;
	REP(i, d) {
		ans += b[i];
	}
	cout << ans << endl;
}


Measured memory_bytes: 11136
nv, ne, r = map(int, input().split())

edges = set(tuple(map(int, input().split())) for _ in range(ne))
costs = [None] * nv
costs[r] = 0

for _ in range(nv - 1):
    for s, t, d in edges:
        if costs[s] is None:
            continue
        cost = costs[s] + d
        if costs[t] is None or costs[t] > cost:
            costs[t] = cost

for s, t, d in edges:
    if costs[s] is None:
        continue
    if costs[s] + d < costs[t]:
        print('NEGATIVE CYCLE')
        break
else:
    for cost in costs:
        print('INF' if cost is None else cost)

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

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		bool[] fix = new bool[N];
		int[] min = new int[N];
		int[] minf = new int[N];
		
		for(int i=0;i<N;i++){
			if(i==0){
				fix[i] = true;
				minf[i] = T[i];
				continue;
			}
			if(i>0 && T[i] != T[i-1]){
				fix[i] = true;
				minf[i] = T[i];
				continue;
			}
			min[i] = T[i];
		}
		for(int i=N-1;i>=0;i--){
			if(i==N-1){
				if(fix[i]){
					if(A[i] != T[i]){
						Console.WriteLine(0);
						return;
					}
				}else{
					if(min[i] >= A[i]){
						minf[i] = A[i];
						fix[i] = true;
						continue;
					}else{
						Console.WriteLine(0);
						return;
					}
				}
			}
			if(i+1<N && A[i]>A[i+1]){
				if(fix[i]){
					if(A[i] != T[i]){
						Console.WriteLine(0);
						return;
					}
				}else{
					if(min[i] >= A[i]){
						minf[i] = A[i];
						fix[i] = true;
						continue;
					}else{
						Console.WriteLine(0);
						return;
					}
				}
			}
			min[i] = Math.Min(min[i],A[i]);
		}
		
		long ans = 1;
		long mod = (long)1e9 + 7;
		for(int i=0;i<N;i++){
			if(fix[i])continue;
			ans *= min[i];
			ans %= mod;
		}
		Console.WriteLine(ans);
		
		
	}
	int N;
	int[] A,T;
	public Sol(){
		N = ri();
		T = ria();
		A = ria();
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}


Measured memory_bytes: 24016
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define INF 0x5555555555555555LL
long long seg[33554432]; int sz;
 
void segtree(int n)
{
    int k;
    k = 1; while (k < n) k <<= 1;
    sz = k;
    memset(seg, (int)INF, sizeof(seg));
}
 
// update kth value to v
void update(int k, long long v)
{
    int t;
    k += sz - 1;
    seg[k] = v;
    while (k > 0) {
        if (!(k & 1)) k--;
        t = k, k >>= 1;
        v = seg[t++]; if (v > seg[t]) v = seg[t];
        seg[k] = v;
    }
}
 
long long _query(int a, int b, int k, int l, int r)
{
    int m;
    long long lmin, rmin;
    if (r <= a || b <= l) return INF;
    if (a <= l && r <= b) return seg[k];
    k <<= 1, m = (l + r) >> 1;
    lmin = _query(a, b, ++k, l, m);
    rmin = _query(a, b, ++k, m, r);
    if (lmin > rmin) lmin = rmin;
    return lmin;
}
 
// get min in [a, b)
long long query(int a, int b)
{
    return _query(a, b, 0, 0, sz);
}
 
 
// セグメントツリー
#define MAX 14350000
typedef struct { long long x, y; } T;
T t[MAX], s[MAX]; int tsz, ssz;
T data[32]; int N;
long long D;
 
// バイナリサーチ
int bsch_lower(long long x)
{
    int m, l = 0, r = ssz;
    while (l < r) {
        m = (l + r) >> 1;
        if (s[m].x <= x) l = m + 1; else r = m;
    }
    return l-1;
}
int bsch_upper(long long x)
{
    int m, l = 0, r = ssz;
    while (l < r) {
        m = (l + r) >> 1;
        if (s[m].x < x) l = m + 1; else r = m;
    }
    return l;
}
 
int span(T *d, int n, T *s)
{
    int i, j, k, sz;
    long long x, y;
 
    if (n <= 0) return 0;
    x = s[0].x, y = s[0].y, sz = 0;
    d[0].x = d[0].y = 0; d[1].x = x, d[1].y = -y; d[2].x = -x, d[2].y = y;
    sz = k = 3;
    for (i = 1; i < n; i++) {
        x = s[i].x, y = s[i].y;
        for (j = 0; j < k; j++) {
            d[sz].x = d[j].x + x, d[sz++].y = d[j].y - y;
            d[sz].x = d[j].x - x, d[sz++].y = d[j].y + y;
        }
        k = sz;
    }
    return sz;
}
 
int cmp(const void *a, const void *b) {
    long long t = ((T *)a)->x - ((T *)b)->x;
    if (t < 0) return -1;
    if (t > 0) return 1;
    return 0;
}
 
int main()
{
    int i, k, l, r;
    long long ans, a;
 
    scanf("%d%lld", &N, &D);
    for (i = 0; i < N; i++) scanf("%lld%lld", &data[i].x, &data[i].y);
    k = N >> 1;
    tsz = span(t, k, data);
    qsort(t, tsz, sizeof(T), cmp);
    ssz = span(s, N-k, data + k);
    qsort(s, ssz, sizeof(T), cmp);
    s[ssz].x = INF;
 
    segtree(ssz);
    for (i = 0; i < ssz; i++) update(i, -s[i].y);
 
    ans = -INF;
    l = bsch_upper(-D - t[0].x); if (l < 0) l = 0;
    r = bsch_lower(D - t[0].x);
 
    for (i = 0; i < tsz; i++) {
        while (s[l].x > -D - t[i].x) l--;
        while (s[l].x < -D - t[i].x) l++;
        while (r >= l && s[r].x > D - t[i].x) r--;
        if (r < l) continue;
        a = -query(l, r + 1) + t[i].y;
        if (a > ans) ans = a;
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 712344
#include <iostream>
#include <algorithm>
#include <cstdlib>

using namespace std;

int main(){
  int N, K;
  int h[100001] = {0};
  int mincostto[100001];
  for(int i=0; i < 100001; i++){
    mincostto[i] = 1000000000;
  }
  cin >> N >> K;
  for(int i=1; i <= N; i++){
    cin >> h[i];
  }
  mincostto[1] = 0;
  mincostto[2] = abs(h[2]-h[1]);
  for(int i=3; i <= N; i++){
    for(int s=K; s >= 1; s--){
      if(i-s < 1) continue;
      mincostto[i] = min(mincostto[i], mincostto[i-s] + abs(h[i] - h[i-s]));
    }
  }
  cout << mincostto[N];
}


Measured memory_bytes: 1024
paper = [[0]*10 for l in range(10)]
while True:
    try:
        x,y,s = map(int, input().split(","))
        # s size
        paper[x][y] += 1
        if y - 1 >= 0:
            paper[x][y - 1] += 1
        if x - 1 >= 0:
            paper[x - 1][y] += 1
        if x + 1 < 10:
            paper[x + 1][y] += 1
        if y + 1 < 10:
            paper[x][y + 1] += 1

        # m size
        if s >= 2:
            if x - 1 >= 0 and y - 1 >= 0:
                paper[x - 1][y - 1] += 1
            if x + 1 < 10 and y - 1 >= 0:
                paper[x + 1][y - 1] += 1
            if x - 1 >= 0 and y + 1 < 10:
                paper[x - 1][y + 1] += 1
            if x + 1 < 10 and y + 1 < 10:
                paper[x + 1][y + 1] += 1

        # l size
        if s >= 3:
            if x - 2 >= 0:
                paper[x - 2][y] += 1
            if x + 2 < 10:
                paper[x + 2][y] += 1
            if y - 2 >= 0:
                paper[x][y - 2] += 1
            if y + 2 < 10:
                paper[x][y + 2] += 1
    except EOFError:
        break
flat_paper = sum(paper, [])
print(flat_paper.count(0))
print(max(flat_paper))



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

/* -------------------------------- Template -------------------------------- */

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

using ll = long long;
using ld = long double;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

template<typename T> T inf() { assert(false); }
template<> constexpr int inf<int>() { return 1e9; }
template<> constexpr ll inf<ll>() { return 1e18; }
template<> constexpr ld inf<ld>() { return 1e30; }

/* -------------------------------- Library -------------------------------- */

/* ---------------------------------- Main ---------------------------------- */

int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  int res = 0;
  REP(i,N) {
    cin >> a[i];
    --a[i];
  }
  REP(i,N) {
    if (a[a[i]] == i) ++res;
  }
  cout << res / 2 << endl;
  return 0;
}


Measured memory_bytes: 768
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int s = sc.nextInt();
    System.out.format("%d:%d:%d\n", s / 60 / 60, s / 60 % 60, s % 60 % 60);
    sc.close();
  }
}


Measured memory_bytes: 26372