akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>

using namespace std;

vector<string> readData(void) {
  int h, w;
  cin >> h >> w;
  vector<string> result;
  for (int i = 0; i < h; ++i) {
    string row;
    cin >> row;
    result.push_back(row);
  }
  return result;
}

int whites(const vector<string>& f) {
  int result = 0;
  for (const auto& g : f) {
    result += count(g.begin(), g.end(), '.');
  }
  return result;
}

using xy = pair<int, int>;

int distance(const vector<string>& f) {
  if (f[0][0] == '#') {
    return -1;
  }
  queue<xy> q;
  vector<vector<int> > dist(f.size(), vector<int>(f[0].size(), -1));
  dist[0][0] = 0;
  q.push(xy(0, 0));
  while (!q.empty()) {
    const int x = q.front().first;
    const int y = q.front().second;
    q.pop();
    int dx = 1, dy = 0, dz = 0;
    for (int i = 0; i < 4; ++i, dz = dx, dx = -dy, dy = dz) {
      const int nx = x + dx, ny = y + dy;
      if (nx < 0 || nx >= f.size() || ny < 0 || ny >= f[0].size()) {
        continue;
      }
      if (f[nx][ny] == '#' || dist[nx][ny] >= 0) {
        continue;
      }
      dist[nx][ny] = dist[x][y] + 1;
      if (nx == f.size() - 1 && ny == f[0].size() - 1) {
        return dist[nx][ny];
      }
      q.push(xy(nx, ny));
    }
  }
  return -1;
}

int main(void) {
  const auto data = readData();
  const int d = distance(data);
  int answer = -1;
  if (d >= 0) {
    answer = whites(data) - (d + 1);
  }
  cout << answer << endl;
  return 0;
}


Measured memory_bytes: 256
{-# LANGUAGE BangPatterns #-}
import Data.List
import Data.Maybe
import Control.Monad
import Data.Function (fix)
import Data.Array (Array, array, (!))
import qualified Data.ByteString as BS
import qualified Data.ByteString.Char8 as BS8
 
getInts :: IO [Int]
getInts = (map parseInt . BS8.words) <$> BS.getLine 
    where parseInt = fst . fromJust . BS8.readInt

data Tree a = Tree (Tree a) a (Tree a)

instance Functor Tree where
    fmap f (Tree l m r) = Tree (fmap f l) (f m) (fmap f r)

index :: Tree a -> Int -> a
index (Tree _ m _) 0 = m
index (Tree l _ r) n = case (n - 1) `divMod` 2 of
    (q,0) -> index l q
    (q,1) -> index r q

nats :: Tree Int
nats = go 0 1
    where go !n !s = Tree (go l s') n (go r s')
            where l = n + s
                  r = l + s
                  s' = s * 2

memo :: (Int -> a) -> (Int -> a)
memo f = index cached
    where cached = fmap f nats

memo2 :: (Int -> Int -> a) -> (Int -> Int -> a)
memo2 f = memo (\x -> memo (f x))

memo3 :: (Int -> Int -> Int -> a) -> (Int -> Int -> Int -> a)
memo3 f = memo (\x -> memo2 (f x))

powerset :: [a] -> [[a]]
powerset = filterM (const [True, False])

split :: [a] -> [Int] -> [[a]]
split str [] = [str]
split str (x:xs) = take x str : split (drop x str) (map (x`subtract`) xs)

solve :: String -> Integer
solve str = sum $ map read $ concatMap (split str) pos
    where pos = powerset [1..length str-1]

main :: IO ()
main = do
    str <- getLine
    print (solve str)

Measured memory_bytes: 1020
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define PB push_back
#define MP make_pair
#define PII pair<int,int>
#define FIR first
#define SEC second
#define ll long long
using namespace std;
template <class T>
inline void rd(T &x) {
	x=0; char c=getchar(); int f=1;
	while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }
	while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
inline ll Abs(ll x) { return x>0?x:-x; }
ll pw[33];
ll sol(ll x1,ll y1,ll x2,ll y2,int d) {
	if(d==0) return Abs(y2-y1);
	ll w=pw[d-1];
	if(x1/w!=x2/w) return Abs(x1-x2)+Abs(y1-y2);
	if(x1/w==1 && Abs(y1/w-y2/w)>=2) return Abs(y1-y2)+min(x1%w+x2%w+2,2*w-x1%w-x2%w);
	return sol(x1%w,y1,x2%w,y2,d-1);
}
int main() {
	pw[0]=1;
	for(int i=1;i<=30;++i) pw[i]=pw[i-1]*3;
	int T; rd(T);
	while(T--) {
		ll x1,y1,x2,y2;
		rd(x1),rd(y1),rd(x2),rd(y2);
		x1--,y1--,x2--,y2--;
		if(Abs(x1-x2)>Abs(y1-y2)) swap(x1,y1),swap(x2,y2);
		printf("%lld\n",sol(x1,y1,x2,y2,30));
	}
	return 0;
}

Measured memory_bytes: 384
N = int(input())

evidence = [[] for _ in range(N)]

for i in range(N):
  a = int(input())
  for _ in range(a):
    x, y = map(int, input().split())
    evidence[i].append([x-1,y])

ans = 0
for i in range(2**N):
  flag = 0
  for j in range(N):
    if ((i>>j) & 1 ):
      for x,y in evidence[j]:
        if (i>>x)&1 != y:
          flag = 1
          break
  if flag == 0:
    ans = max(ans, bin(i)[2:].count('1'))
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18,MOD = 1e9 + 7;
const int INT_INF = 1e9,INT_MOD=1e9+7;
#define rep(i, N) for(int i = 0; i < N; i++)
typedef pair<int, int> Pi;
typedef pair<double, double> P;
signed main(){
    int n;cin>>n;
    int a[n];
    rep(i,n) cin>>a[i];
    int flag=-1;
    rep(i,n){
        if(a[i]%2==0){
            if(a[i]%3!=0 and a[i]%5!=0)flag=1;
        }
    }
    if(flag<0) cout<<"APPROVED"<<endl;
    else cout<<"DENIED"<<endl;
    return 0;
}

Measured memory_bytes: 256
/**
 *
 * AtCoder Beginner Contest 103 - Problem D: Islands War (https://abc103.contest.atcoder.jp/tasks/abc103_d)
 *
 * Maximize the function f(x) = (x mod a1) + (x mod a2) + ... + (x mod aN) where x, a1, .., aN 
 * are positive integers.
 *
 * Math solution: The modular system of equations X = -1 (mod a1) always has unique solution mod
 * m = [a1, a2, ..., aN] equals to (m - 1). Thus we must add (ai - 1) for all ai.
 */
#include <iostream>
#include <algorithm>

using namespace std;
using ii = pair<int, int>;

const int MAX { 100010 };
ii as[MAX];

void solve(int M)
{
    sort(as, as + M);
    auto ans = 0, last = 0;

    for (int i = 0; i < M; ++i)
    {
        auto R = as[i].first;
        auto L = as[i].second;

        if (L < last)
            continue;

        ++ans;
        last = R;
    }

    cout << ans << endl;
}

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

    int N, M;
    cin >> N >> M;

    for (int i = 0; i < M; ++i)
        cin >> as[i].second >> as[i].first;

    solve(M);

    return 0;
}


Measured memory_bytes: 1024
;; E - Change a Little Bit

(defun main ()
  (let* ((N (read))
         (C (loop repeat N collect (read))))
    (princ (solve N C))
    (fresh-line)))

(defparameter *modulus* (+ (expt 10 9) 7))

(defun solve (N C)
  (let ((expt-4-N-1
         (loop for i below N
               for e = 1 then (mod (* e 4) *modulus*)
               finally (return e)))) ; 2^{2N-2} (= 4^{N-1})
    (setf C (sort C #'<))
    (mod (loop for cost in C
               for i from 0
               sum (* cost expt-4-N-1 (- (1+ N) i)))
         *modulus*)))

(main)


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

using namespace std;

int main()
{
	int x;
	cin >> x;
	for (long long i = 0;; i++)
	{
		if (i * (i + 1) / 2 >= x)
		{
			cout << i << endl;
			break;
		}
	}

	return 0;
}


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

using namespace std;

using ll = long long;

bool judge(vector<int>& a, vector<int>& b, int n) {
    for (int i = 0; i < n; i++) {
        if (a[i] != b[i]) return false;
    }
    return true;
}

const int INF = 60;

int dp[51][51];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    for (int j = 0; j <= 50; j++) {
        for (int i = 0; i < j; i++) {
            dp[i][j] = INF;
        }

        for (int i = j + 1; i <= min(2 * j, 50); i++) {
            dp[i][j] = INF;
        }
        if (2 * j + 1 <= 50) dp[2 * j + 1][j] = j + 1;

        for (int i = j + 1; i <= 50; i++) {
            dp[i][j] = INF;
            for (int k = 1; k <= i; k++) {
                dp[i][j] = min(dp[i][j], max(k, dp[i % k][j]));
            }
        }
    }

    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];

    using P = pair<int, int>;
    vector<set<P> > s(n);
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        if (dp[a[i]][b[i]] == INF) {
            ans = -1;
            break;
        }
        s[i].emplace(dp[a[i]][b[i]], a[i]);
    }

    if (ans == -1) {
        cout << ans << endl;
        return 0;
    }

    //int pv = 0;
    while (!judge(a, b, n)) {
        int maxv = 0;
        for (int i = 0; i < n; i++) {
            maxv = max(maxv, s[i].begin()->first);
        }
        //assert(maxv != pv && (pv == 0 || maxv < pv));
        //pv = maxv;
        if (maxv == 0) break;
        ans |= (1LL << maxv);
        for (int i = 0; i < n; i++) {
            vector<P> hoge;
            for (auto& p : s[i]) {
                if (p.first == maxv) {
                    hoge.push_back(p);
                }
                if (p.second >= maxv && dp[p.second % maxv][b[i]] < maxv) {
                    s[i].emplace(dp[p.second % maxv][b[i]], p.second % maxv);
                }
            }
            for (P& p : hoge) s[i].erase(p);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
 
int main(void)
{
  float x,y,z;
   
  scanf("%f",&x);
  
  scanf("%f",&y);
  
  z=(4*x-y)/2;
  
  if((z>=0&&z<=x)&&(int)z==z)
  {
    printf("Yes");
  }else{
    printf("No");
  }
  return 0;
}

Measured memory_bytes: 1716
n,m=map(int,input().split())
edge=[[]for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edge[a].append(b)
  edge[b].append(a)
ans=[a+1,b+1]
visited={a,b}
s=b
while 1:
  flag=True
  for i in edge[s]:
    if i in visited:continue
    visited.add(i)
    flag=False
    ans.append(i+1)
    s=i
    break
  if flag:break
ans=ans[::-1]
s=a
while 1:
  flag=True
  for i in edge[s]:
    if i in visited:continue
    visited.add(i)
    flag=False
    ans.append(i+1)
    s=i
    break
  if flag:break
print(len(ans))
print(*ans)

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

using namespace std;


int main()
{
  
  long long int n,i,min=10000000000000000;
  scanf("%lld",&n);
  
  for(i=1;i<=sqrt(n);++i)
    {
        if(n%i==0)
          {
              if(min>(i-1+n/i-1))
                 min=(i-1+n/i-1);
          }
    }
    
    printf("%ld",min);
   
     
    
}

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

int main(){
  string s;
  cin >> s;
  int a=0, b=0, c=0;
  for(char k:s){
    if(k=='a')a=1;
    if(k=='b')b=1;
    if(k=='c')c=1;
  }
  if(a+b+c==3)cout << "Yes";
  else cout << "No";
  return 0;
}


Measured memory_bytes: 256
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <limits>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x * x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

int main() {
	int n, m; cin >> n >> m;
	vector<vector<int>> d(n, vector<int>(m));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> d[i][j];
		}
	}

	set<int> s;
	for (int i = 0; i < 10000; i++) {
		s.insert(i*i);
	}

	int ans = 0;

	for (int i = 0; i < n; i++) {
		for (int j = i+1; j < n; j++) {
			int val = 0;
			for (int k = 0; k < m; k++) {
				int diff = abs(d[i][k] - d[j][k]);
				val += diff * diff;
			}

			if (s.count(val))ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

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

using namespace std;

typedef long long int ll;

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

  ll n, m;
  cin >> n >> m;
  vector < ll > a(n);
  for(int i = 0; i < n; i++){
    cin >> a[i];
    a[i] /= 2;
  }
  ll lcm = 1;
  for(int i = 0; i < n; i++){
    lcm = (a[i] * lcm) / __gcd(a[i], lcm);
  }

  bool ok = true;
  for(int i = 0; i < n; i++){
    ll b = lcm / a[i];
    if(b % 2 == 0) ok = false;
  }

  if(ok){
    ll lo = 0, hi = 1e9, k = 0;
    while(lo <= hi && lcm <= m){
      ll mid = (hi - lo) / 2 + lo;
      if((2 * mid - 1) * lcm <= m){
        k = max(k, mid);
        lo = mid + 1;
      }else hi = mid - 1;
    }

    cout << k << endl;
  }else{
    cout << 0 << '\n';
  }
}


Measured memory_bytes: 1024
s = input()
n = len(s) + 1

a = [-1] * n
tmp = 0

if s[0] == '<':
    a[0] = 0
if s[-1] == '>':
    a[-1] = 0

for i in range(1,n-2):
    if s[i] == '>' and s[i+1] == '<':
        a[i+1] = 0

for i in range(n-1):
    if a[i] == 0:
        tmp = 1
    else:
        tmp += 1
    if s[i] == '<':
        a[i+1] = tmp
    else:
        tmp = 0

for i in range(n-1):
    i = i * (-1) - 1
    if a[i] == 0:
        tmp = 1
    else:
        tmp += 1
    if s[i] == '>':
        a[i-1] = max(tmp, a[i-1])
    else:
        tmp = 0

print(sum(a))


Measured memory_bytes: 29208
#include <bits/stdc++.h>
using namespace std;
 typedef long long ll;
 
int main() {
int n;
cin>>n;
int m[200000];
for(int i=0;i<n;i++){
cin>>m[i];
}
int type = 1;
int ans=1;
for(int i=1;i<n;i++){

if(m[i-1]<m[i]){
if(type == 2){
    type=1;
ans++;
}
else {
    type=0;
}
}
else if(m[i-1]>m[i]){
if(type==0){
type=1;
ans++;
}
else{
    type=2;
}
}

}
cout<<ans<<endl;

}

Measured memory_bytes: 640
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define max(p,q) ((p)>(q)?(p):(q))
#define min(p,q) ((p)<(q)?(p):(q))
#define chmax(a,b) ((a)=(a)>(b)?(a):(b))
#define chmin(a,b) ((a)=(a)<(b)?(a):(b))
#define abs(p) ((p)>=(0)?(p):(-(p)))
#define MOD 1000000007
ll powll(ll a,ll b){ll r=1;rep(i,b){r*=a;}return r;}
#define swap(a,b) do{ll w=(a);(a)=(b);(b)=w;}while(0)
#define swapd(a,b) do{double w=(a);(a)=(b);(b)=w}while(0)
#define in(a) scanf("%lld", &(a))
#define in2(a,b) scanf("%lld %lld",&(a),&(b))
#define in3(a,b,c) scanf("%lld %lld %lld",&(a),&(b),&(c))
#define ind(a) scanf("%lf", &(a))
#define ins(a) scanf("%s", (a))
#define put(a) printf("%lld\n", (a))
#define putd(a) printf("%.15f\n", (a))
//      puts(a) printf("%s\n", a) 文字はこっち
//your code here!
int main(void){
    ll N, f=0;
    in(N);
    ll n = N;
    while(N>0){
        f += N%10;
        N /= 10;
    }
    puts(n%f ? "No":"Yes");
    return 0;
}


Measured memory_bytes: 128
x1,y1,x2,y2 = list(map(int,input().split()))
vectorX = x2 - x1
vectorY = y2 - y1
x3 = x2 - vectorY
y3 = y2 + vectorX
x4 = x3 - vectorX
y4 = y3 - vectorY
answer = str(x3) + " " + str(y3) + " " + str(x4) + " " + str(y4)
print(answer)

Measured memory_bytes: 8880
#include<cstdio>
#include<vector>
#include<algorithm>
#include<map>

using namespace std;

using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;
using vll=vector<ll>;
using vvll=vector<vll>;
using vpii=vector<pii>;


int main(void)
{
	int x;
	while(scanf("%d", &x)==1)
	{
		map<ll,int> m;

		for(int i=-1000;i<=1000;i++) m[((ll)i*i*i*i*i)]=i;

		for(auto mm:m)
		{
			auto it=m.find(mm.first+x);
			if(it==m.end()) continue;

			printf("%d %d\n", it->second, mm.second);
			break;
		}
	}
	return 0;
}


Measured memory_bytes: 3420
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N = II()
    D = LI()
    mod = 998244353

    C = [0] * (N+1)
    for d in D:
        C[d] += 1
    # print(C)

    # 木が存在するかを判定
    ans = 1
    p = C[0]
    if not(D[0] == 0 and p == 1):
        print(0)
        return
    for i in range(1, N):
        ci = C[i]
        p = ci
        ans = ans * pow(C[i], C[i+1], mod)
    print(ans % mod)


    

if __name__ == '__main__':
    solve()


Measured memory_bytes: 20668
#include <stdio.h>
int main(void)
{
    int a,b,ans=0;
    scanf("%d%d", &a, &b);
    for(int i=0; i<2; i++)
    {
        if(a>b)
        {
            ans+=a;
            a--;
        }
        else
        {
            ans+=b;
            b--;
        }
    }
    printf("%d", ans);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int n;
int a[200007];
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	printf("%d ",a[n]);
	int ans=0;
	for (int i=1;i<n;i++)
		if (min(a[i],a[n]-a[i])>min(ans,a[n]-ans)) ans=a[i];
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <math.h>
using namespace std;

int main (){
    int a, b;
    cin >> a >> b;
    if(a+b >= a-b && a+b >= a*b){
        cout << a+b;
    }else if(a-b>= a+b && a-b >= a*b){
        cout << a-b;
    }else if(a*b >= a+b && a*b >= a-b){
        cout << a*b;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int A,B,C,D;
  cin >> A >> B >> C >> D;

  if (A+B > C+D){
    cout << "Left" << endl;
  }
  else if( A+B < C+D ){
    cout << "Right" << endl;
  }
  else{
    cout<< "Balanced" << endl;
  }

  
}


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

int cost[100000] = {};
int calc[100000] = {};
int h[100000] = {};

int jump(int pos) {
    // cout << pos << endl;
    if (calc[pos] == 1) {
        return cost[pos];
    }
    if (pos <= 1) {
        return 0;
    } else if (pos == 2) {
        return jump(pos-1) + abs(h[pos-1] - h[pos]);
    } else {
        cost[pos] = min(jump(pos-1) + abs(h[pos-1] - h[pos]),
                        jump(pos-2) + abs(h[pos-2] - h[pos]));
    }
    calc[pos] = 1;
    return cost[pos];
}

int main() {
    int n;
    cin >> n;
    h[0] = 0;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        h[i+1] = x;
    }
    cout << jump(n) << endl;
    return 0;
}


Measured memory_bytes: 2944
#include <bits/stdc++.h>
using namespace std;
#define REP(i,N) for(i=0;i<N;i++)
#define INF 1e9
typedef long long ll;

int main(void){
  ll N,M;cin >> N >> M;
  vector<ll> A(N);
  vector<ll> S(N+1);
  S[0] = 0;
  int i;REP(i,N){
    cin >> A[i];
    S[i+1] = S[i]+A[i];
  }
  map<ll,int> m;
  REP(i,N){
    if(m.count(S[i+1]%M)>0) m[S[i+1]%M]++;
    else m[S[i+1]%M] = 1;
  }
  ll sum=0;
  for(auto i = m.begin();i!=m.end();i++){
    ll n = i->second;
    if(i->first==0) sum += n;
    sum += n*(n-1)/2;
  }
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 5760
a = gets.to_i
b = gets.to_i
c = gets.to_i
x = gets.to_i
ans = 0
for i in 0..a
	for j in 0..b
		for k in 0..c
			if 500 * i + 100 * j + 50 * k == x
				ans += 1
			end
		end
	end
end
puts ans

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

using ll = long long;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define ddrep(i, n) for (int i = n; i > 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)
#define ssrep(i, s, t) for (int i = s; i <= t; ++i)

#define rng(a) a.begin(), a.end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second

#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))

using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using ld = long double;

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "{";
  rep(i, (int)v.size()) {
    if (i)
      os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}

template <typename T, size_t S> void printArray(const T (&array)[S]) {
  for (auto val : array)
    std::cout << val << ", ";
  std::cout << "\n";
}

const int mod = 1e9 + 7;
const int inf = 1e9 + 5;

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

  int a, b; std::cin >> a >> b;
  std::cout << ((a * b) & 1 ? "Odd" : "Even") << "\n";
}


Measured memory_bytes: 256
// input! macro from
// 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)*}
    };
}

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)*}
    };
}

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")
    };
}


fn main () {
    input!{
        a: usize,
        b: usize,
    }
    let ans = if b % a == 0 {a + b} else {b - a};
    println!("{}", ans);
}

Measured memory_bytes: 4352
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <list> 
#include<algorithm>
#include<cmath>
#include<map>
#include<vector>
#include<string>
#include<fstream>
#include<set>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define forl(i,a,n) for(int i=a;i<n;i++)
#define rfor(i,n,a) for(int i=n;i>=a;i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define ld long double
#define vi vector<int>
#define vll vector<long long>
#define pi pair<int,int>
#define pll pair<long long,long long>
#define mp make_pair
#define B begin()
#define E end()
#define S size()
#define m9 1000000007
#define endl "\n"
using namespace std;
 
 

 
ll gcd(ll x,ll y)
{
    if(x==0) return y;
    return gcd(y%x,x);
}

ll powmod(ll x, ll y, ll m) 
{ 
    if (y == 0) 
        return 1; 
    ll p = powmod(x, y/2, m) % m; 
    p = (p * p) % m; 
    return (y%2 == 0)? p : (x * p) % m; 
} 

 
ll mul_inv(ll a, ll b) {
    ll b0 = b, t, q;
    ll x0 = 0ll, x1 = 1ll;
    if (b == 1ll) return 1ll;
    while (a > 1ll) {
        q = a / b;
        t = b, b = a % b, a = t;
        t = x0, x0 = x1 - q * x0, x1 = t;
    }
    if (x1 < 0ll) x1 += b0;
    return x1;
}
 
 
#define p0(a) cout << a << " "
#define p1(a) cout << a << endl
#define p2(a, b) cout << a << " " << b << endl
#define p3(a, b, c) cout << a << " " << b << " " << c << endl
#define p4(a, b, c, d) cout << a << " " << b << " " << c << " " << d << endl
#define pin(a) for(auto x:a)cout<<x<<" ";cout<<endl
#define fck(a) cout<<a;exit(0)
#define vvll vector<vector<ll> >
#define A(b) b.begin(),b.end()
#define vpi std::vector<pll>
#include <array>
#include <stack>
#define arr2 array<ll,2>
#define arr3 array<ll,3>
#define varr2 vector<array<ll,2> >
#define varr3 vector<array<ll,3> >
//include<bits/stdc++.h>
 
 
bool fa(vll &x,vll &y){return x[0]<y[0];}
bool fa1(vll &x,vll &y){return x[1]<y[1];}
bool f1(pll &x,pll &y){return x.second>y.second;}
bool f2(pll &x,pll &y){
    return x.first>y.first;
}
 
 
bool f3(ll &x,ll &y){
    return x>y; 
    }


const ll maxn=2e5+2;





int main()
{ fastio;
//freopen("input.txt, "r", stdin); 
//freopen("output.txt", "w", stdout);

ll n;cin>>n;
vll b;
forl(i,0,n){
    ll x,y;cin>>x>>y;
    b.pb(x==y)
;}
ll ans=0;
ll cnt=0;
forl(i,0,n){
    if(b[i]==0){
        ans=max(ans,cnt);
        cnt=0;
    }
    else{
        cnt++;
    }
}
        ans=max(ans,cnt);

if(ans>=3){
    cout<<"Yes\n";
}
else{
    cout<<"No\n";
}



return 0;
}





  







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

int main()
{
	int val[100] = {0};
	int i;
	while(cin >> i){
		val[i]++;
	}
	int rec=0;
	for(int i=0;i<100;i++)
		rec = max(rec,val[i]);
	for(int i=0;i<100;i++)
		if(val[i]==rec)
			cout << i << endl;
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
 
using namespace std;
#define repr(i,a,b) for (int i=a; i<b; i++)
#define rep(i,n) for (int i=0; i< (int) n; i++)
#define PI  3.14159265358979323846264338327950
 
 
int main () {
    int N;
    cin >> N;
    string tmp;
    unordered_map<string, int> s;
    rep(i,N){
        cin >> tmp;
        s[tmp]++;
    }

    int M;
    cin >> M;
    unordered_map<string,int> t;
    rep(i,M){
        cin >> tmp;
        t[tmp]++;
    }

    int ans =0;
    for(auto & d : s){
        ans = max(ans, d.second-t[d.first]);
    }

      cout << ans << endl;
    return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	cout << "? 10000000000" << endl; 
	char c; cin >> c; 
	if(c == 'Y'){
		long long now = 9; 
		for(int i = 0; i < 114514; i++){
			cout << "? " << now << endl; 
			char d; cin >> d; 
			if(d == 'Y'){
				cout << "! " << (now + 1) / 10 << endl; 
				return 0; 
			}
			now *= 10; now += 9; 
		}
	}else{
		long long now = 10; 
		for(int i = 0; i < 114514; i++){
			cout << "? " << now << endl; 
			char d; cin >> d; 
			if(d == 'N') break; 
			now *= 10; 
		}
		long long ng = now / 10; 
		long long ok = now - 1; 
		while(ok - ng > 1){
			long long mid = (ng + ok) / 2; 
			cout << "? " << mid * 10 << endl; 
			char d; cin >> d; 
			if(d == 'Y') ok = mid; 
			else ng = mid; 
		}
		cout << "! " << ok << endl; return 0;
	}
}

Measured memory_bytes: 3736
#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
//#define cerr if(false) cerr
#ifdef DEBUG
#define show(...) cerr << #__VA_ARGS__ << " = ", debug(__VA_ARGS__);
#else
#define show(...) 42
#endif
using namespace std;
using ll = long long;
using pii = pair<int, int>;
template <typename T, typename S>
ostream& operator<<(ostream& os, pair<T, S> a) {
    os << '(' << a.first << ',' << a.second << ')';
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for (auto x : v) os << x << ' ';
    return os;
}
void debug() {
    cerr << '\n';
}
template <typename H, typename... T>
void debug(H a, T... b) {
    cerr << a;
    if (sizeof...(b)) cerr << ", ";
    debug(b...);
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<vector<int>>g(n);
    string s;
    cin >> s;
    rep(i,m){
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    queue<int>q;
    rep(i,n)q.push(i);
    vector<bool>erase(n);
    while(q.size()){
        int x = q.front();
        q.pop();
        if(erase[x])continue;
        set<char>st;
        for(int i : g[x]){
            if(!erase[i])st.insert(s[i]);
        }
        if(st.size() <= 1){
            erase[x] = true;
            for(int i : g[x]){
                if(!erase[i]){
                    q.push(i);
                }
            }
        }
    }
    rep(i,n){
        if(!erase[i]){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    
}

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

using namespace std;

int D[333][333][333];
char str[333];
int n, k;

int f(int l, int r, int t)
{
	if(l >= r) return l == r;
	
	if(D[l][r][t]) return D[l][r][t];
	
	int ret = max(f(l+1, r, t), f(l, r-1, t));
	if(str[l] == str[r]) ret = max(ret, f(l+1, r-1, t) + 2);
	else if(t < k) ret = max(ret, f(l+1, r-1, t+1) + 2);
	
	return D[l][r][t] = ret;
}

int main()
{
	scanf("%s%d", str, &k);
	
	for(;str[n];n++);
	
	printf("%d\n", f(0, n-1, 0));
	
	return 0;
}

Measured memory_bytes: 131200
N, M = map(int, input().split())
ans = []
lst = []
start = 0 if N == 1 else 10**(N-1)
for i in range(M):
    a, b = map(int, input().split())
    lst.append([a, b])


for i in range(start, 10**N):
    flag = True
    for j in range(M):
        if str(i)[lst[j][0]-1] != str(lst[j][1]):
            flag = False
            break
    
    if flag == True:
        print(i)
        exit()

print(-1)

Measured memory_bytes: 3064
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        for (int i= 0;i < n;i++) {
            a[i] = sc.nextInt();
            b[i] = a[i];
        }

        Arrays.sort(b);
        int max1 = b[b.length - 1];
        int max2 = b[b.length - 2];
        for (int i = 0;i<n;i++) {
            if (a[i] == max1) {
                System.out.println(max2);
            } else {
                System.out.println(max1);
            }
        }

    }
}

Measured memory_bytes: 88176
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(c) (c).begin(),(c).end()
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define MINF(a) memset(a,0x3f,sizeof(a))
#define POW(n) (1LL<<(n))
#define IN(i,a,b) (a <= i && i <= b)
using namespace std;
template <typename T> inline bool CHMIN(T& a,T b) { if(a>b) { a=b; return 1; } return 0; }
template <typename T> inline bool CHMAX(T& a,T b) { if(a<b) { a=b; return 1; } return 0; }
template <typename T> inline void SORT(T& a) { sort(ALL(a)); }
template <typename T> inline void REV(T& a) { reverse(ALL(a)); }
template <typename T> inline void UNI(T& a) { sort(ALL(a)); a.erase(unique(ALL(a)),a.end()); }
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-10;
/* ---------------------------------------------------------------------------------------------------- */

int N,M;
vector<int> G[100010];
int S,T;
int dis[100010][3];

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  cin >> N >> M;
  REP(i,M) {
    int u,v;
    cin >> u >> v;
    u--; v--;
    G[u].push_back(v);
  }
  cin >> S >> T;
  S--; T--;

  MINF(dis);
  dis[S][0] = 0;
  using P = tuple<int,int,int>;
  priority_queue<P,vector<P>,greater<P>> que;
  que.emplace(0,S,0);
  while (!que.empty()) {
    int dd,v,k;
    tie(dd,v,k) = que.top(); que.pop();
    if (dis[v][k] < dd) continue;
    for (int nv : G[v]) {
      if (CHMIN(dis[nv][(k+1)%3],dis[v][k]+1)) {
        que.emplace(dis[nv][(k+1)%3],nv,(k+1)%3);
      }
    }
  }
  cout << (dis[T][0] == INF ? -1 : dis[T][0]/3) << endl;

  return 0;
}

Measured memory_bytes: 8820
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
#include <numeric>

using namespace std;
#define ALL(x)			(x).begin(),(x).end()
#define REP(i, n)		for (int (i) = 0 ; (i) < (ll)(n) ; ++(i))
#define REPN(i, m, n)	for (int (i) = m ; (i) < (ll)(n) ; ++(i))
#define INF				(int)2e9
#define MOD				(1000 * 1000 * 1000 + 7)
#define Ceil(x, n)		(((((x))+((n)-1))/n))		/* Nの倍数に切り上げ割り算 */
#define CeilN(x, n)		(((((x))+((n)-1))/n)*n)		/* Nの倍数に切り上げ */
#define FloorN(x, n)	((x)-(x)%(n))				/* Nの倍数に切り下げ */
#define IsOdd(x)		(((x)&0x01UL) == 0x01UL)			
#define IsEven(x)		(!IsOdd((x)))						
#define M_PI			3.14159265358979323846
typedef long long		ll;
typedef pair<ll, string>	P;
typedef vector<ll>		VLL;
typedef vector<VLL>		VVLL;
typedef vector<VVLL>	VVVLL;

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

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

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

	CombInit();

	ll maxR = min(n, k);
	ll ans = 1;
	REPN(i, 1, maxR + 1) {
		ll zeroCmb = CombExec(n, i);
		ll sikiriNum = n - i - 1;
		ll oneCmb = CombExec(n - 1, sikiriNum);
		ans += (zeroCmb * oneCmb);
		ans %= MOD;
	}

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


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

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

int main() {
	string s;
	cin >> s;
	int ans = 0;
	rep(i, s.length() / 2) {
		if (s[i] != s[s.length() - i - 1])ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3580
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<ll,ll> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 100000000000000000
int c[10];
int main(void){
    for(int i=0;i<4;i++){
        int a;
        cin>>a;
        c[a]++;
    }
    if(c[1]==1&&c[9]==1&&c[7]==1&&c[4]==1)cout<<"YES\n";
    else cout<<"NO\n";
}


Measured memory_bytes: 256
import java.util.Scanner;

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

    if(X < A) {
      System.out.println(0);
    } else {
      System.out.println(10);
    }
  }
}

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

using namespace std;

const long long MOD = 1e9 + 7;

int dp[100100];

int main(){
  int N; cin >> N;
  vector<int> A(N);
  memset(dp,0,sizeof(dp));

  for(int i = 0; i < N; i++){
    int a; cin >> a; 
    if((N - 1 - a) % 2 != 0){ cout << 0 << endl; return 0;}
    if( a == 0){ 
      if( dp[0] >= 1){ cout << 0 << endl; return 0;}
      else{ dp[0]++;}}
    
    else if( dp[a] >= 2){ cout << 0 <<endl; return 0;}
    else{
      dp[a]++;}
  }
  
  
  long long ans = 1;
  for(int i = 1; i < 100100; i++){
    if( dp[i] != 0 ){ ans *= 2; ans %= MOD;}}
  
  cout << ans << endl; return 0;}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(V) V.begin(),V.end()
#define MOD 998244353

ll D[15][15];
ll R[15], C[15];

int main() {
	ll N, M, X, A, mn = LLONG_MAX;
	cin >> N >> M >> X;
	for (int i = 0;i < N;i++) {
		cin >> C[i];
		for (int j = 0;j < M;j++) {
			cin >> D[i][j];
		}
	}

	for (int i = 0;i < (1 << N);i++) {
		A = 0;
		for (int j = 0;j < N;j++) {
			if (i & (1 << j)) {
				A += C[j];
				for (int k = 0;k < M;k++) {
					R[k] += D[j][k];
				}
			}
		}
		for (int k = 0;k < M;k++) {
			if (R[k] < X) {
				A = LLONG_MAX;
			}
			R[k] = 0;
		}
		mn = min(A, mn);
	}
	if (mn == LLONG_MAX) {
		cout << -1 << endl;
	}
	else {
		cout << mn << endl;
	}
}


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

using ll = long long;
using ld = long double;
#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 REP(i, n) FOR(i, 0, (n))
#define REPR(i, n) FORR(i, (n) - 1, 0)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define REPS(c, s) for (char c : s)
#define ALL(c) (c).begin(), (c).end()
#define sz(v) (int)v.size()
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;}
const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000001000000001LL;
const char EOL = '\n';

void solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(numeric_limits<double>::max_digits10);
    solve();
    return 0;
}

void solve() {
    ll t1, t2, a1, a2, b1, b2;
    cin >> t1 >> t2 >> a1 >> a2 >> b1 >> b2;

    ll f = (a1 - b1) * t1;
    ll s = (a2 - b2) * t2;
    if (f + s == 0) {
        cout << "infinity" << EOL;
        return;
    }
    if (f < 0) {
        f = -f;
        s = -s;
    }
    if (f + s > 0) {
        cout << 0 << EOL;
//    } else if (f * 2 < abs(s)) {
//        cout << 1 << EOL;
//    } else if (f * 2 == abs(s)) {
//        cout << 2 << EOL;
    } else {
        ll t = f / abs(f + s);
        ll r = f % abs(f + s);
        cout << t * 2 + (r == 0 ? 0 : 1) << EOL;
    }
}



Measured memory_bytes: 256
//minamoto
#include<bits/stdc++.h>
#define R register
#define inline __inline__ __attribute__((always_inline))
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
const int N=10005;
typedef long long ll;
struct node{
	int w,s,v;
	inline bool operator <(const node &b)const{return s-b.w>b.s-w;}
}a[N];
int n,mx;ll res,f[N];
inline int min(R int x,R int y){return x<y?x:y;}
int main(){
	scanf("%d",&n);
	fp(i,1,n)scanf("%d%d%d",&a[i].w,&a[i].s,&a[i].v);
	sort(a+1,a+1+n);
	fp(i,1,n){
		fp(j,a[i].w,10000)cmax(f[min(j-a[i].w,a[i].s)],f[j]+a[i].v);
		cmax(f[a[i].s],1ll*a[i].v);
	}
	fp(i,0,10000)cmax(res,f[i]);
	printf("%lld\n",res);
	return 0;
}

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

int main(){
  int N;
  long long L0, L1, L2;
  cin >> N;
  L2 = 2;
  L1 = 1;

  if(N == 1){
    cout << 1 << endl;
  }
  else {
    for(int i = 0;i < N - 1; i++){
      L0 = L1 + L2;
      
      L2 = L1;
      L1 = L0;
    }
    cout << L0 << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
template<class T> void chmin(T& a,const T& b){if(a>b)a=b;}
template<class T> void chmax(T& a,const T& b){if(a<b)a=b;}
string s;
int rui[100100];
#define MAX_N 200100
struct BIT{
	ll bit[MAX_N+1];
	void init(){
		memset(bit,0,sizeof(bit));
	}
	void add(int i,ll x){
		i++;
		while(i<=MAX_N){
			bit[i]+=x;
			i+=i&-i;
		}
		return;
	}
	ll sum(int i){
		i++;
		ll res=0;
		while(i>0){
			res+=bit[i];
			i-=i&-i;
		}
		return res;
	}
	ll sum(int l,int r){// [l,r]
		if(l==0)return sum(r);
		else return sum(r)-sum(l-1);
	}
};
const int GETA = 100000;
P solve(char c){
	BIT bit;
	bit.init();
	for(int i=0;i<s.size();i++){
		if(s[i]==c)rui[i]=1;
		else rui[i]=-1;
	}
	for(int i=0;i<s.size();i++){
		rui[i+1]+=rui[i];
	}
	bit.add(GETA,1);
	int b = -1;
	for(int i=1;i<s.size();i++){
		if(bit.sum(GETA+rui[i]-1)>0){
			b=i;
			break;
		}
		bit.add(GETA+rui[i-1],1);
	}
	if(b==-1)return P(-1,-1);
	if(rui[b]>0)return P(0,b);
	for(int i=0;i<b;i++){
		if(rui[i]<rui[b]){
			return P(i+1,b);
		}
	}
}
int main(){
	cin >> s;
	for(int i=0;i<27;i++){
		char c = 'a'+i;
		P ans = solve(c);
		if(ans.fi!=-1){
			//cout << c << endl;
			cout << ans.fi+1 << ' ' << ans.sec+1 << endl;
			return 0;
		}
	}
	cout << "-1 -1" << endl;
	return 0;
}

Measured memory_bytes: 2432
N = int(input())
A = [int(d) for d in input().split()]

MOD = int(1e9+7)

A_cum = [0]
for i in range(N):
    A_cum.append((A_cum[-1] + A[i]) % MOD)

ans = 0
for i in range(N-1):
    t = (A[i] * (A_cum[-1] - A_cum[i+1]) % MOD ) % MOD
    ans = (t + ans)% MOD

print(ans)

Measured memory_bytes: 31500
#include <stdio.h>

int a, b;
int n;
int x, y;

int dp[32][32];
int i, j;

int main()
{
	while (scanf("%d %d", &a, &b)){
		
		if (a == 0 && b == 0) break;

		for (i = 0; i <= 16; i++){
			for (j = 0; j <= 16; j++){
				dp[i][j] = 0;
			}
		}

		scanf("%d", &n);
		for (i = 0; i < n; i++){
			scanf("%d %d", &x, &y);
			dp[y][x] = -1;
		}

		dp[1][1] = 1;
		for (i = 1; i <= b; i++){
			for (j = 1; j <= a; j++){
				if (dp[i][j] == -1) {
					dp[i][j] = 0;
					continue;
				}

				dp[i][j] += dp[i - 1][j] + dp[i][j - 1];
			}
		}

		printf("%d\n", dp[b][a]);
	}

	return (0);
}

Measured memory_bytes: 604
import sys
INF = 1 << 60
MOD = 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

prime = 998244353
root = 3
def _fmt(A, inverse = False):
    N = len(A)
    logN = (N - 1).bit_length()
    base = pow(root, (prime - 1) // N * (1 - 2 * inverse) % (prime - 1), prime)
    step = N
    for k in range(logN):
        step >>= 1
        w = pow(base, step, prime)
        wj = 1
        nA = [0] * N
        for j in range(1 << k):
            for i in range(1 << logN - k - 1):
                s, t = i + j * step, i + j * step + (N >> 1)
                ps, pt = i + j * step * 2, i + j * step * 2 + step
                nA[s], nA[t] = (A[ps] + A[pt] * wj) % prime, (A[ps] - A[pt] * wj) % prime
            wj = (wj * w) % prime
        A = nA
    return A

def convolution(f, g):
    N = 1 << (len(f) + len(g) - 2).bit_length()
    Ff, Fg = _fmt(f + [0] * (N - len(f))), _fmt(g + [0] * (N - len(g)))
    N_inv = pow(N, prime - 2, prime)
    fg = _fmt([a * b % prime * N_inv % prime for a, b in zip(Ff, Fg)], inverse = True)
    del fg[len(f) + len(g) - 1:]
    return fg

class modfact(object):
    def __init__(self, n):
        fact, invfact = [1] * (n + 1), [1] * (n + 1)
        for i in range(1, n + 1): fact[i] = i * fact[i - 1] % MOD
        invfact[n] = pow(fact[n], MOD - 2, MOD)
        for i in range(n - 1, -1, -1): invfact[i] = invfact[i + 1] * (i + 1) % MOD
        self._fact, self._invfact = fact, invfact

    def fact(self, n):
        return self._fact[n]

    def invfact(self, n):
        return self._invfact[n]

    def comb(self, n, k):
        return self._fact[n] * self._invfact[k] % MOD * self._invfact[n - k] % MOD if 0 <= k <= n else 0

    def perm(self, n, k):
        return self._fact[n] * self._invfact[n - k] % MOD if 0 <= k <= n else 0

from collections import Counter
def resolve():
    n = int(input())
    H = [int(input()) for _ in range(2 * n)]

    mf = modfact(2 * n)
    doublefact = [1] * (2 * n + 10)
    for i in range(2, 2 * n + 1):
        doublefact[i] = i * doublefact[i - 2] % MOD

    F = []
    for k in Counter(H).values():
        f = []
        for i in range(k // 2 + 1):
            f.append(mf.comb(k, 2 * i) * doublefact[2 * i - 1] % MOD)
        F.append(f)

    for i in range(len(F) - 1):
        F.append(convolution(F[2 * i], F[2 * i + 1]))

    f = F.pop()
    ans = 0
    for i in range(len(f)):
        f[i] = f[i] * doublefact[2 * n - 2 * i - 1] % MOD
        if i & 1:
            ans -= f[i]
        else:
            ans += f[i]
    ans %= MOD
    print(ans)
resolve()

Measured memory_bytes: 135040
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N,K,R,S,P;
  cin>>N>>K>>R>>S>>P;
  string T;
  cin>>T;
  int sum=0;
  for(int i=0;i<N;i++){
    if(T.at(i)=='r'){
      sum=sum+P;
    }
    else if(T.at(i)=='s'){
      sum=sum+R;
    }
    else{
      sum=sum+S;
    }
  }
  for(int i=0;i<N-K;i++){
    if(T.at(i)==T.at(i+K)){
      if(T.at(i)=='r'){
        sum=sum-P;
        T.at(i+K)='d';
      }
      else if(T.at(i)=='s'){
        sum=sum-R;
        T.at(i+K)='d';
      }
      else if(T.at(i)=='p'){
        sum=sum-S;
        T.at(i+K)='d';
      }
    }
  }
  cout<<sum<<endl;
}

Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

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

	cin >> N >> K;

	vector<int> x(N, 0);

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

	cout << sum << endl;

    return 0;
}



Measured memory_bytes: 256
n, a, b = map(int, input().split())
x = a * n - a + b
y = b * n - b + a


if a > b:
    print(0)
elif a == b and n == 1:
    print(1)
elif a != b and n == 1:
    print(0)
else:
    print(y - x + 1)


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

int main(){
    int N, K;
    cin >> N >> K;
    int cnt = 0;
    while(true){
        N /= K;
        cnt++;
        if(N == 0){
            break;
        }
    }
    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int main(){
  long long a;
  cin >> a;
  long long copy = a,ctemp = a;
  vector<int> v;
  long long w = 2;
  while(a!=1&&w*w<=copy){
    int cnt = 0;
    while(a%w==0){
      cnt++;
      a /= w;
    }
    if(cnt!=0){
      v.push_back(cnt);
    }
    w += (w%2) + 1;
  }
  
  if(copy==1){
    cout << 0 << endl;
    return 0;
  }
  if(a==copy){
    cout << 1 << endl;
    return 0;
  }
  long long ans = 0;
  for(int i=0;i<v.size();i++){
    int p = 1;
    while(v[i]-p>=0){
      ans++;
      v[i] -= p;
      p++;
    }
  }
  if(a!=1) ans++;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3632
import java.util.Scanner;
import java.util.Arrays;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int[] num = new int[n + 1];
		int variety = 0;
		for(int i = 0; i < n; i++) {
			int ball = sc.nextInt();
			if(num[ball] == 0) {
				variety++;
			}
			num[ball]++;
		}

		Arrays.sort(num);

		int ans = 0;
		int i = 0;
		while(variety > k) {
			if(num[i] != 0) {
				ans += num[i];
				variety--;
			}
			i++;
		}
		System.out.println(ans);
	}
}


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

using namespace std;
string str;
int l,r;
int main()
{
	cin>>str;
	for(int i=0;i<str.length();i++)
		if(str[i] == 'A') {
			l = i; break;
		}
	for(int i=str.length()-1;i>=0;i--)
		if(str[i] == 'Z') {
			r = i; break;
		}
	cout<<r-l+1<<endl;
	return 0;
}

Measured memory_bytes: 640