akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int maxn = 4000 + 10;
int n, k;
ll inv[maxn], fac[maxn], facinv[maxn], ans[maxn];
void init()
{
	inv[0] = inv[1] = 1;
	fac[0] = facinv[0] = 1;
	for(int i = 1; i < maxn; ++i)
		fac[i] = fac[i - 1] * i % mod;
	for(int i = 2; i < maxn; ++i)
		inv[i] = (mod - mod / i) * inv[mod % i] % mod;
	for(int i = 1; i < maxn; ++i)
		facinv[i] = facinv[i - 1] * inv[i] % mod;
}
ll C(ll m, ll n)
{
	return fac[m] * facinv[m - n] % mod * facinv[n] % mod;
}
ll norm(ll x)
{
	while(x > 0) x -= mod;
	while(x < 0) x += mod;
	return x;
}
int main()
{
	init();
	scanf("%d%d", &k, &n);
	for(int j = 2; j <= k + 1; ++j)
	{
		ll ret = 0;
		int t = j >> 1;
		for(int i = 0; i <= t && n - 2 * i >= 0; ++i)
		{
			ll tmp = C(t, i) * C(n - 2 * i + k - 1, k - 1) % mod;
			if(i & 1)
				ret = norm(ret - tmp);
			else
				ret = norm(ret + tmp);
 		}
 		ans[j] = ans[2 * k - j + 2] = ret;
 	}
 	for(int j = 2; j <= 2 * k; ++j)
 		printf("%lld\n", ans[j]);
 	return 0;
}

Measured memory_bytes: 384
#include <algorithm>
#include <boost/optional.hpp>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i, n) for(int i = 0, i##_MACRO = (n); i < i##_MACRO; i++)
#define RANGE(i, a, b) for(int i = (a), i##_MACRO = (b); i < i##_MACRO; i++)
#define EACH(e, a) for(auto&& e : a)
#define ALL(a) std::begin(a), std::end(a)
#define RALL(a) std::rbegin(a), std::rend(a)
#define FILL(a, n) memset((a), n, sizeof(a))
#define FILLZ(a) FILL(a, 0)
#define INT(x) (static_cast<int>(x))
#define PRECISION(x) std::fixed << std::setprecision(x)

using namespace std;

using ll = long long;
using VI = std::vector<int>;
using VI2D = std::vector<vector<int>>;
using VLL = std::vector<long long>;
using VLL2D = std::vector<vector<long long>>;

constexpr int INF = 2e9;
constexpr double EPS = 1e-10;
constexpr double PI = acos(-1.0);

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

template <typename T>
constexpr int sign(T x) {
	return x < 0 ? -1 : x > 0 ? 1 : 0;
}

template <>
constexpr int sign(double x) {
	return x < -EPS ? -1 : x > EPS ? 1 : 0;
}

template <typename T, typename U>
constexpr void chmax(T& m, U x) {
	m = max(m, x);
}

template <typename T, typename U>
constexpr void chmin(T& m, U x) {
	m = min(m, x);
}

template <typename T>
constexpr T square(T x) {
	return x * x;
}

int main() {
	int n;
	cin >> n;
	VLL a(n);
	REP(i, n) { cin >> a[i]; }

	cout << (all_of(ALL(a), [](int x) { return x % 2 == 0; }) ? "second"
															  : "first")
		 << endl;

	return 0;
}


Measured memory_bytes: 4068
import sys
input = sys.stdin.readline
from collections import *

def compress(l):
    l = list(set(l))
    l.sort()
    idx = defaultdict(int)
    
    for i in range(len(l)):
        idx[l[i]] = i
    
    return idx
    
class BIT:
    #n:要素数
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    #i番目(0-indexed)の値にxを足す
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] += x
            i += i&(-i)
    
    #sum[0, i)
    def acc(self, i):
        s = 0
        
        while i>0:
            s += self.bit[i]
            i -= i&(-i)
        
        return s

Q = int(input())
que = []
vals = []

for _ in range(Q):
    l = list(map(int, input().split()))
    que.append(l)
    
    if len(l)==3:
        vals.append(l[1])

idx = compress(vals)
rev_idx = defaultdict(int)

for k, v in idx.items():
    rev_idx[v] = k
    
N = len(list(idx.keys()))
bit1 = BIT(N)
bit2 = BIT(N)
b_acc = 0
cnt = 0

for i in range(Q):
    if len(que[i])==3:
        a, b = que[i][1], que[i][2]
        b_acc += b
        bit1.add(idx[a], 1)
        bit2.add(idx[a], a)
        cnt += 1
    else:
        l, r = 0, N-1
        
        while l<=r:
            m = (l+r)//2
            
            if bit1.acc(m+1)>=(cnt+1)//2:
                r = m-1
            else:
                l = m+1
        
        x = l
        lsum = bit1.acc(x)*rev_idx[x]-bit2.acc(x)
        rsum = bit2.acc(N)-bit2.acc(x)-(bit1.acc(N)-bit1.acc(x))*rev_idx[x]
        print(rev_idx[x], lsum+rsum+b_acc)

Measured memory_bytes: 119764
import java.util.HashSet;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		HashSet<Integer>aset = new HashSet<Integer>();
		HashSet<Integer>bset = new HashSet<Integer>();
		
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		for(int i = 0; i< m ; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			if(a == 1) {
				bset.add(b);
				}
			if(b == n) {
				aset.add(a);
			}
		}
		sc.close();
		
		aset.retainAll(bset);
		
		if(!aset.isEmpty()) {
			System.out.println("POSSIBLE");
		}
		else {
			System.out.println("IMPOSSIBLE");
		}
	
	}
	

	
}



Measured memory_bytes: 105372
#define _USE_MATH_DEFINES
#include  <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include<math.h>
#include<iomanip>
#include<stdio.h>
#include <stdlib.h>
#include<stdio.h>
#include <queue>
#include<map>
#include <sstream>
#include<set>
#include<stack>
typedef long long int ll;
//#include<bits/stdc++.h>


using namespace std;

vector<long long int>a(500005), b(500005);



int main()
{
    
    string p;
    cin >> p;
    int a = 0;
    int n = p.size();
    for (int i = 0; i < p.size() / 2; i++) {
        if (p[i] == p[n - i - 1])continue;
        a++;
    }
    cout << a << endl;

    return 0;

}

Measured memory_bytes: 10988
//入力マクロここから
//https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules ! input_inner { ( $ next : expr ) => { } ; ( $ next : expr , ) => { } ; ( $ next : expr , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ next , $ t ) ; input_inner ! { $ next $ ( $ r ) * } } ; }
macro_rules ! read_value { ( $ next : expr , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ next , $ t ) ) ,* ) } ; ( $ next : expr , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ next , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ next : expr , chars ) => { read_value ! ( $ next , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ next : expr , usize1 ) => { read_value ! ( $ next , usize ) - 1 } ; ( $ next : expr , $ t : ty ) => { $ next ( ) . parse ::<$ t > ( ) . expect ( "Parse error" ) } ; }
macro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut iter = $ s . split_whitespace ( ) ; let mut next = || { iter . next ( ) . unwrap ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { let stdin = std :: io :: stdin ( ) ; let mut bytes = std :: io :: Read :: bytes ( std :: io :: BufReader :: new ( stdin . lock ( ) ) ) ; let mut next = move || -> String { bytes . by_ref ( ) . map ( | r | r . unwrap ( ) as char ) . skip_while ( | c | c . is_whitespace ( ) ) . take_while ( | c |! c . is_whitespace ( ) ) . collect ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; }
//入力マクロここまで

use std::cmp::*;

fn main() {
    input! {
        n: usize,
        a: [i64;n],
    }

    let mut sunuke = a[0];
    let mut arai = a[1..n].iter().sum::<i64>();
    let mut ans = (sunuke - arai).abs();

    for i in 1..n - 1 {
        sunuke += a[i];
        arai -= a[i];
        ans = min(ans, (sunuke - arai).abs());
    }

    println!("{}", ans);
}


Measured memory_bytes: 6396
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

void solve() {
  int N, M;
  cin >> N >> M;

  vector<vector<int>> V(N+1);
  vector<int> income(N+1);
  vector<int> parent(N+1);


  for (int i = 0; i < N-1+M; i++) {
    int a, b; cin >> a >> b;
    V[a].push_back(b);
    income[b]++;
  }

  int root = 1;
  while (income[root] > 0) {
    root++;
  }

  parent[root] = 0;

  queue<int> q;
  q.push(root);

  while (!q.empty()) {
    int x = q.front(); q.pop();

    for (int dist : V[x]) {
      income[dist]--;
      if (income[dist] == 0) {
        q.push(dist);
        parent[dist] = x;
      }
    }
  }

  for (int i = 1; i <= N; i++) {
    cout << parent[i] << endl;
  }
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  solve();
  return 0;
}


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

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

    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a.at(i);

    sort(a.begin(), a.end());

    double sum = a.at(0);
    for (int i = 1; i < n; i++) {
        sum = (sum + a.at(i)) / 2;
    }

    cout << sum << endl;

    return 0;
}


Measured memory_bytes: 3700
#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
int main(){
  int n,m;
  cin>>n>>m;
  char a[n][m];
  for(int i=0;i<n;i++)
    for (int j=0;j<m;j++)
      cin>>a[i][j];
  int dp[n][m];
  memset(dp,0,sizeof dp);
  dp[0][0]=1;
  for(int i=1;i<m;i++) {
    if(a[0][i]=='#') continue;
    dp[0][i]+=dp[0][i-1];
    dp[0][i]%=mod;
  }
  for(int i=1;i<n;i++){
    if(a[i][0]=='#') continue;
    dp[i][0]+=dp[i-1][0];
    dp[i][0]%=mod;
  }
  for(int i=1;i<n;i++){
  	for(int j=1;j<m;j++){
      if(a[i][j]=='#') continue;
      dp[i][j]=dp[i-1][j]+dp[i][j-1];
      dp[i][j]%=mod;
    }  	
  }
  
  cout<<dp[n-1][m-1];
}
  

Measured memory_bytes: 5120
s = str(input())

t = len(s)
s = s[:t-1]
for _ in range(t):
    if len(s) % 2 != 0:
        s = s[:len(s)-1]
        continue
    if s[:(len(s)//2)] == s[len(s)//2:]:
        print(len(s))
        break
    else:
        s = s[:len(s)-2]

Measured memory_bytes: 3060
#!/usr/bin/env python3
#!/usr/bin/env pypy3

from math import *

def main():
    import sys
    sys.dont_write_bytecode = True
    sys.setrecursionlimit(10000000)
    from sys import stdin, stdout, stderr
    input = stdin.readline

    #import numpy as np
    #import scipy as sp

    # Python 3 modules: https://docs.python.org/3/library/

    import os
    import math, itertools, operator
    from math import factorial as fact
    from operator import itemgetter, attrgetter
    from itertools import permutations, combinations
    from functools import reduce, lru_cache
    # Use scipy for stats: https://docs.scipy.org/doc/scipy/reference/stats.html
    # Before Python 3.5.  Import from math after it.
    from fractions import gcd
    from fractions import Fraction as Frac

    inf = float('inf')

    def lcm(a, b):
        return a * b // gcd(a,b)

    def perm(a, b):
        import scipy.special
        return scipy.special.perm(a, b, exact = True)

    def comb(a, b):
        import scipy.special
        return scipy.special.comb(a, b, exact = True)

    def dfact(n):
        import scipy.special
        return scipy.special.factorial2(n, exact = True)

    def prod(l):
        return reduce(operator.mul, l)

    def input_ints(func = input, sep = None, conv = int):
        return list(map(conv, func().split(sep = sep)))

    #if os.environ.get('GOROOT') is None:
    if 1:
        def dprint(*args, **kwargs):
            kwargs['file'] = sys.stderr
            import inspect
            frame = inspect.currentframe().f_back
            print('[' + os.path.basename(frame.f_code.co_filename)
                    + ':' + str(frame.f_lineno) + ']', *args, **kwargs)
    else:
        def dprint(*args, **kwargs):
            pass


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


    S = input()
    dprint(S)
    for i in range(len(S) - 1):
        dprint(S[i])
        if S[i] == S[i+1]:
            print('Bad')
            return
    print('Good')


if __name__ == '__main__':
    main()


Measured memory_bytes: 5824
#include <stdio.h>
 
int main(void)
{   int a,b,i;
    char op;
    for(i=1;i>0;i++){
        scanf("%d %c %d",&a,&op,&b);
        if(op=='+')
        {printf("%d\n",a+b);
        }
        else if(op=='-')
        {printf("%d\n",a-b);
        }
        else if(op=='*')
        {printf("%d\n",a*b);
        }
        else if(op=='/'){
            printf("%d\n",a/b);
        }else if(op=='?') {
            break;
        }
    }
    return 0;
}



Measured memory_bytes: 2104
import sys
sys.setrecursionlimit(10**9)

read=sys.stdin.read
class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.dist=[0]*n 
    
    def find(self,x):
        if self.parents[x]<0:
            return self.dist[x],x
        else:
            tmp=self.find(self.parents[x])
            self.dist[x]+=tmp[0]
            self.parents[x]=tmp[1]
            return self.dist[x], self.parents[x]
    
    def union(self,x,y,d):
        rx=self.find(x)[1]
        ry=self.find(y)[1]
        diff=self.dist[y]-self.dist[x]-d
        if rx==ry:
            if diff!=0:
                return True
            return False
        if diff<0:
            rx,ry=ry,rx
            diff=-diff
        self.parents[ry]=min(self.parents[ry],self.parents[rx]-diff)
        self.parents[rx]=ry
        self.dist[rx]=diff
        return False
    
def main():
    n,m,*lrd=map(int,read().split())
    v=Unionfind(n)
    for l,r,d in zip(*[iter(lrd)]*3):
        if v.union(l-1,r-1,d):
            print('No')
            break
    else:
        print('Yes')
if __name__=='__main__':
    main()


Measured memory_bytes: 74488
#include<bits/stdc++.h>
using namespace std;
int x[900][900],h,w,a,y[900],s,i,j;
queue<int>Q,R;
int main(){
while(true){
memset(x,0,sizeof(x));
memset(y,0,3600);
cin>>w>>h;
if(!w){break;}
for(i=0;i<h*2-1;i++){
if(i%2==1){
for(j=0;j<w;j++){
cin>>a;
if(!a){
x[(i/2)*30+j][(i/2+1)*30+j]=1;
}
}
}
else{
for(j=0;j<w-1;j++){
cin>>a;
if(a==0){
x[(i/2)*30+j][(i/2)*30+j+1]=1;
}
}
}
}
Q.push(0);
s=1;
y[0]=1;
while(y[(h-1)*30+(w-1)]==0){
while(!Q.empty()){
a=Q.front();
for(int j=0;j<900;j++){
if((x[a][j]||x[j][a])&&!y[j]){
y[j]=1;
R.push(j);
}
}
Q.pop();
}
while(!R.empty()){
Q.push(R.front());
R.pop();
}
s++;
if(s>999){s=0;break;}
}
while(!Q.empty()){
Q.pop();
}
cout<<s<<endl;
}
}

Measured memory_bytes: 4388
import java.util.*;
 
class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int q = s.nextInt();
 
        Queue<String> queP = new LinkedList<String>();
        Queue<Integer> queT = new LinkedList<Integer>();
 
        int time = 0;
 
        for (int i = 0; i < n; i++) {
            queP.add(s.next());
            queT.add(s.nextInt());
        }
 
        while (queP.size() != 0) {
            if (queT.peek() - q >0) {
                queP.add(queP.poll());
                queT.add(queT.poll()-q);
                time += q;
            }else {
                time += queT.poll();
                System.out.println(queP.poll() + " " + time);
            }
        }
    }
}



Measured memory_bytes: 75508
import Data.List
import Data.Char
import Data.Maybe
import qualified Data.ByteString.Char8 as BS8

main :: IO ()
main = do
    a <- fst . fromJust . BS8.readInteger <$> BS8.getLine
    s <- getLine

    putStrLn $ if a >= 3200
        then s
        else "red"


Measured memory_bytes: 380
def solve(n, traffic_list):
    min_val = min(traffic_list)
    if n % min_val == 0:
        return n // min_val + len(traffic_list) - 1
    else:
        return n // min_val + len(traffic_list)


def main():
    n = int(input())
    a = int(input())
    b = int(input())
    c = int(input())
    d = int(input())
    e = int(input())

    ans = solve(n, [a, b, c, d, e])
    print(ans)


main()


Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
using namespace std;
using ll = long long;

int main() {
    cin.tie(0); ios_base::sync_with_stdio(false);
    ll N,M,K;cin>>N>>M>>K;
    if(K==0 || K==M*N) {
        cout << "Yes" << '\n';
        return 0;
    }
    for(int n = 1; n<=N; ++n){
        for(int m = 0; m < M; ++m){
             ll black = n*M + (-n + N-n) * m;
             if(black==K){
                 cout << "Yes" << '\n';
                 return 0;
             }
        }
    }
    for(int m = 1; m <= M; ++m){
        for(int n = 0; n < N; ++n){
            ll black = m*N + (-m + M-m) * n;
            if(black==K){
                cout << "Yes" << '\n';
                return 0;
            }
        }
    }
    cout << "No" << '\n';
    return 0;
}

Measured memory_bytes: 256
import java.io.*;
import java.math.*;

class Main {
	public static void main(String args[]) throws IOException {
		InputStreamReader isr = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(isr);
		
		int n = Integer.parseInt(br.readLine());
		
		long min = 0;
		long max = 0;
		long sum = 0;
		long input_num;
		
		String input = br.readLine();
		String[] sz_num = input.split(" ");
		
		for (int i = 0; i < n; i++) {
			int tmp = Integer.parseInt(sz_num[i]);
			
			if (i == 0 || min > tmp) {
				min = tmp;
			}
			if (i == 0 || max < tmp) {
				max = tmp;
			}
			
			sum += Long.valueOf(tmp);
		}
		
		System.out.println(min +" "+ max +" "+ sum);
	}
}

Measured memory_bytes: 28832
#include<iostream>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

int dp[15][1<<15];
pair<int,int> prv[15][1<<15];
bool g[15][15];
int n,m;
int s,t;
int k[15];
vector<int> r[15];
int light;
int INF = (1<<10);

string itos(int a){
  if(!a)return "0";
  string res;
  while(a){
    res += a%10 + '0';
    a/=10;
  }
  for(int i=0;i<(int)res.size()/2;i++)swap(res[i],res[(int)res.size()-1-i]);
  return res;
}

int main(){
  while(cin >> n >> m && (n || m)){
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)g[i][j] = false;

    for(int i=0;i<m;i++){
      cin >> s >> t;
      s--;t--;
      g[s][t] = g[t][s] = true;
    }

    light = 0;
    for(int i=0;i<n;i++){
      int tmp;
      cin >> tmp;
      light += (tmp<<i);
    }

    for(int i=0;i<n;i++){
      cin >> k[i];
      r[i].clear();
      r[i].resize(k[i]);
      for(int j=0;j<k[i];j++){
	cin >> r[i][j];
	r[i][j]--;
      }
      sort(r[i].begin(),r[i].end());
    }

    for(int i=0;i<n;i++)
      for(int j=0;j<(1<<n);j++){
	dp[i][j] = INF;
	prv[i][j] = make_pair(-1,-1);
      }
    dp[0][light] = 0;

    queue<pair<int,int> > q;
    q.push(make_pair(0,light));

     
    if(!(light&1)){
      cout << "Help me!\n";
      continue;
    }
    
    while(q.size()){
      pair<int,int> p = q.front();q.pop();
      int room = p.first, state = p.second;

      for(int i=0;i<k[room];i++){
	if(r[room][i]==room)continue;
	int tmp = 1<<r[room][i];
	int hoge = state;
	if(state & tmp)hoge -= tmp;
	else hoge += tmp;
	if(dp[room][hoge] > dp[room][state]+1){
	  dp[room][hoge] = dp[room][state]+1;
	  prv[room][hoge] = make_pair(room,state);
	  q.push(make_pair(room,hoge));
	}
      }

      for(int j=0;j<n;j++){
	if(g[room][j] && (state & (1<<j))){
	  if(dp[j][state] > dp[room][state]+1){
	    dp[j][state] = dp[room][state]+1;
	    prv[j][state] = make_pair(room,state);
	    q.push(make_pair(j,state));
	  }
	}
      }
    }
    
    int m = INF;
    for(int i=0;i<(1<<n);i++)m = min(m,dp[n-1][i]);
    if(m==INF)cout << "Help me!\n";
    else if(dp[n-1][1<<(n-1)]==INF)cout << "You can not switch off all lights.\n";
    else{
      cout << "You can go home in " << dp[n-1][1<<(n-1)] << " steps.\n";

      vector<string> ans;
      int room = n-1,state = 1<<(n-1);
      for(;;){
	int prvr = prv[room][state].first;
	int prvs = prv[room][state].second;
	if(prvr<0 && prvs<0)break; 
	if(prvr != room)ans.push_back("Move to room " + itos(room+1) + ".\n");
	else{
	  for(int i=0;i<n;i++){
	    if( (prvs & (1<<i)) && !(state & (1<<i)) ){
	      ans.push_back("Switch off room " + itos(i+1) + ".\n");
	    }else if( !(prvs & (1<<i)) && (state & (1<<i)) ){
	      ans.push_back("Switch on room " + itos(i+1) + ".\n");
	    }
	  }
	}
	room = prvr;
	state = prvs;
      }
      for(int i=(int)ans.size()-1;i>=0;i--)cout << ans[i];
    }
  }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)n;i++)
using Graph = vector<vector<int> >;
using GraphC = vector<vector<char> >;
const int INF = 1000000000;
typedef pair<int, int> P;
const int MAX_N = 1000000000;
const int MAX_V = 100000000;
typedef int64_t ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int N;
map<string, int> score;

int main() {
	cin >> N;
	rep(i, N) {
		string tmp;
		cin >> tmp;
		score[tmp] += 1;
	}

	int cnt = 0;
	for(auto it : score) {
		cnt = max(cnt, it.second);
	}

	for (auto it : score) {
		if (it.second== cnt)
		{
			cout << it.first << endl;
		}
	}
}

Measured memory_bytes: 19140
#include <string>
#include <iostream>
#include <stack>
#include <queue> // priority_queue も入ってる
#include <set>   // 要素数は size() で取得 multisetもある
#include <map>
#include <array> // sizeはコンパイル時定数で固定
#include <vector>
#include <numeric>   // accumulate, gcd
#include <algorithm> // count_ifに必要
#include <iomanip>   // cout << setprecision(15) << x で小数の出力精度を指定
#include <tuple>
#include <utility> //pair
#include <cmath>
#include <random>

using namespace std;
// 問題が起こるまでintは使用禁止2020-04-13
using ll = long long;

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

template <class InputIterator, class T>
bool contains_itr(InputIterator iterator, const T &value)
{
    if (find(iterator.begin(), iterator.end(), value) == iterator.end())
        return false;
    else
        return true;
}

template <class T>
bool contains_set(set<T> st, const T &value)
{
    if (st.find(value) == st.end())
    {
        return false;
    }
    else
    {
        return true;
    }
}

template <class InputIterator>
auto sum(InputIterator iterator)
{
    return accumulate(iterator.begin(), iterator.end(), 0);
}

// endは排他的(exclusive)なので注意
vector<ll> range(ll begin, ll end)
{
    vector<ll> result;
    for (ll i = begin; i < end; ++i)
    {
        result.push_back(i);
    }
    return result;
}

random_device seed_gen;
mt19937 engine(seed_gen());
// 0, 1, 2 のどれかが得られる一様分布
// uniform_int_distribution<> dist(0, 2);
// cout << dist(engine) << endl;
// みたいに、先に確率分布を宣言して、そこにengineを与えて使う。

// =========ここまでテンプレ============

int main()
{
    ll n, m;
    cin >> n >> m;
    vector<ll> a(m);
    vector<ll> b(m);
    rep(i, m)
    {
        cin >> a[i];
        cin >> b[i];
        --a[i];
        --b[i];
    }
    vector<vector<ll>> targets(n);
    rep(i, m)
    {
        targets[a[i]].push_back(b[i]);
        targets[b[i]].push_back(a[i]);
    }
    ll result = 0;
    vector<bool> includedFlags(n, false);
    rep(i, n)
    {
        if (includedFlags[i] == false)
        {
            ll count = 0;
            includedFlags[i] = true;
            ++count;
            queue<ll> que;
            que.push(i);
            while (!que.empty())
            {
                ll now = que.front();
                que.pop();
                rep(j, targets[now].size())
                {
                    if (includedFlags[targets[now][j]] == false)
                    {
                        includedFlags[targets[now][j]] = true;
                        ++count;
                        que.push(targets[now][j]);
                    }
                }
            }
            result = max(result, count);
        }
    }
    cout << result << endl;
    return 0;
}

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

int main(){
  int H, W;
  cin >> H >> W;
  vector<string> photo;
  string frame;
  for(int i = 0; i < W + 2; i++){
    frame += '#';
  }
  photo.push_back(frame);
  for(int i = 0; i < H; i++){
    string raw, tempraw;
    raw += '#';
    cin >> tempraw;
    raw += tempraw;
    raw += '#';
    photo.push_back(raw);
  }
  photo.push_back(frame);
  for(int i = 0; i < photo.size(); i++){
    cout << photo.at(i) << endl;
  }
}

Measured memory_bytes: 3644
#include <iostream>
#include <cstdio>
#define N 100005
using namespace std;

int q, c[N];
bool v[N];
int main()
{
	int i, j, t1, t2;
	for (i = 2; i < N; i++) {
		for (j = 2; j * j <= i; j++) if (i % j == 0) break;
		if (j * j > i) v[i] = 1;
	}
	for (i = 3; i < N; i += 2) {
		if (v[i] && v[(i + 1) / 2]) c[i]++;
		c[i] += c[i - 2];
	}
	cin >> q;
	while (q--) {
		scanf("%d %d", &t1, &t2);
		printf("%d\n", c[t2] - c[t1 - 2]);
	}
    return 0;
}

Measured memory_bytes: 1152
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <map>
#include <unordered_map>
#define rep(i, n) for (int i = 0; i < n; i++)
#define all(a) (a).begin(), (a).end()
typedef long long ll;
using namespace std;
const int N = 2e5 + 5;
 
using namespace std;

int main() 
{
     int n,ans=1000000000;
     cin>>n;

     int a[n+5];

        for(int i=0; i<n; i++) cin>>a[i];
 
        for(int i=-100;i<=100;i++)
        {
            int cost=0;
            for(int j=0;j<n;j++)
            {
               cost+=(i-a[j])*(i-a[j]);
            }
            ans=min(ans,cost);
        }
         cout<<ans<<endl;
    
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7;




int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    string s[] = {"SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"};
    string x;
    cin >> x;
    int ans = 0;
    for(int i = 0; i < 7; i++) if(s[i] == x) ans = i;
    cout << 7 - ans;

    return 0;
}


Measured memory_bytes: 3548
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-ffloat-store")  
#pragma GCC optimize ("-fno-defer-pop")
typedef long long int ll; 
typedef long double ld; 


int main()
{
	std::ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	ll a;
	string s;
	cin>>a>>s;
	
	if(a<3200)
	{
		cout<<"red"<<endl;
	}
	else{
		cout<<s<<endl;
	}
	
}




Measured memory_bytes: 256
/* Bismillahirrahmanirrahim */
/* Author : Jehian Norman Saviero (@Reiva5) */
#include <bits/stdc++.h>

// MACROS SAMPAH
#define Jehian using
#define Norman namespace
#define Saviero std

Jehian Norman Saviero;

// MACROS TYPE
typedef long l;
typedef long long ll;
typedef unsigned long ul;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<l,l> pl;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<l> vl;
typedef vector<ll> vll;

// MACROS FOR PRINT
#define nl printf("\n")
#define sp printf(" ")

// MACROS FOR ATTRIBUTE
#define fi first
#define se second

// MACROS FOR FUNCTION AND METHOD
#define eb emplace_back
#define mp make_pair
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define ALL(x) (x).begin(), (x).end()
#define ALLN(x,n) (x), (x)+(n)
#define CUBE(x) (SQR(x)*(x))
#define SET(x,y) for (int _qwe = sizeof(x)/sizeof(x[0]); _qwe; ) x[--_qwe] = (y)
#define SQR(x) ((x)*(x))
#define SSORT(x,sz) sort(ALLN(x,sz))
#define RESET(x) memset((x), 0, sizeof(x))
#define VSORT(x) sort(ALL(x))

// MACROS READ INPUT
#define sci(x) scanf("%d", &x)
#define scl(x) scanf("%ld", &x)
#define scll(x) scanf("%lld", &x)
#define scul(x) scl(x)
#define scull(x) scll(x)

int main() {
	int arr[3];
	for (int i = 0; i < 3; ++i) sci(arr[i]);
	SSORT(arr,3);
	printf("%d\n", arr[0]+arr[1]);
	return 0;
}

Measured memory_bytes: 256
import numpy as np

def test(x, A, F):
	return np.clip(A - x // F, 0, None).sum() <= K

if __name__ == "__main__":
	N, K = map(int, input().split())
	A = np.array([int(a) for a in input().split()])
	F = np.array([int(a) for a in input().split()])
	A = np.sort(A)
	F = np.sort(F)[::-1]
	left = -1
	right = 10**12 + 1
	while left + 1 < right:
		mid = (left + right) // 2
		if test(mid, A, F):
			right = mid
		else:
			left = mid
	ans = right
	print(ans)

Measured memory_bytes: 37268
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <utility>
#include <numeric>
#include <queue>
#include <stack>

using ll = long long;
using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr ll MOD_LL = ll(1e9 + 7);

int main(void) {
	int n;
	string s;
	cin >> n >> s;
	
	int ans = 0;
	for(int i = 0; i < 1000; ++i) {
		string tmp;
		
		if( i == 0 ) {
			tmp = "000";
		} else if( i > 0 && i < 10 ) {
			tmp = "00";
			tmp += (char)(i + '0');
		} else if( i >= 10 && i < 100 ) {
			tmp = '0';
			tmp += to_string(i);
		} else {
			tmp = to_string(i);
		}
		
		int k = 0;
		for(int j = 0; j < n; ++j) {
			if( s[j] == tmp[k] ) k++;
			if( k == 3 ) break;
		}
		
		if( k == 3 ) ans++;
	}
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 3772
program security
  implicit none
  character(4) :: s
  read(*,*) s
  if (s(1:1).eq.s(2:2).or.s(2:2).eq.s(3:3).or.s(3:3).eq.s(4:4)) then
    write(*,'(a)') "Bad"
  else
    write(*,'(a)') "Good"
  end if
  stop
end program security

Measured memory_bytes: 768
/* Author: Dhruv Rastogi */
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define all(sdk) sdk.begin(),sdk.end()
#define mll map<int, int>
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;++i)
#define repd(i,a,b) for(int i=a;i>=b;--i)
#define mp make_pair
#define hell 1000000007
#define endl '\n'
#define vvll vector<vector<int> >
#define vll vector<int>
#define mint map<int,int> 
#define sz(x) (int)x.size()
#define sll set<int>
#define pll pair<int,int>
#define F first
#define S second
const long double PI = acos(-1.0);

pll a[100005];
void solve(){  
	int n;
	cin>>n;
	rep(i,0,n){
		cin>>a[i].F;
		a[i].S=i;
	}
	sort(a,a+n);
	rep(i,0,n) cout<<a[i].S+1<<' ';
	cout<<endl;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 2432
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <map>
using ll = long long;
int MOD = 1e9 + 7;
using namespace std;
int main()
{
    int k,t;
    cin>>k>>t;
    vector<int> vec(t);
    for(int i=0;i<t;i++){
        cin>>vec[i];
    }
    sort(vec.begin(),vec.end(),greater<int>());
    int x=k-vec[0];
    cout<<max(0,vec[0]-x-1)<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define endl ("\n")
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ms memset
#define MOD 1000000007
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define fr(i,n) for(i=0;i<n;i++)
#define si(x)	scanf("%d",&x)
#define sl(x)	scanf("%lld",&x)
#define ss(s)	scanf("%s",s)
#define pi(x)	printf("%d\n",x)
#define pl(x)	printf("%lld\n",x)
#define ps(s)	printf("%s\n",s)
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pl;
typedef vector<int>	vi;
typedef vector<ll>	vl;
typedef vector<pii>	vpii;
typedef vector<pl>	vpl;
typedef vector<vi>	vvi;
typedef vector<vl>	vvl;
#define OJ \
    freopen("input.txt", "r", stdin); \
    freopen("output.txt", "w", stdout);

ll expo (ll x, ll y) {ll res = 1; while (y) {if (y & 1)res = res * x; res %= MOD; y = y >> 1; x = x * x; x %= MOD;} return res;}

void solve()
{   
   ll i,j;
   ll n;
   cin>>n;
   ll A[n+1][3],dp[n+1][3];
   fr(i,n+1)
   cin>>A[i+1][0]>>A[i+1][1]>>A[i+1][2];
    dp[1][0]=A[1][0];
    dp[1][1]=A[1][1];
    dp[1][2]=A[1][2];
    for(i=2;i<=n;i++)
    {
        dp[i][0]=A[i][0]+max(dp[i-1][1],dp[i-1][2]);
        dp[i][1]=A[i][1]+max(dp[i-1][0],dp[i-1][2]);
        dp[i][2]=A[i][2]+max(dp[i-1][0],dp[i-1][1]);
    }
    cout<<max(max(dp[n][0],dp[n][1]),dp[n][2])<<endl;
   
}

int main() 
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin); 
    freopen("output.txt", "w", stdout);
#endif
    fast;
    // Fuck Ratings, I'm in Love with Experience. 
    int t = 1;
    //cin >> t;
    while(t--) {
      solve();
    }
    return 0;
}



Measured memory_bytes: 8336
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n)]
cd = [list(map(int,input().split())) for _ in range(m)]
student = []
for i in range(n):
    ans = []
    for j in range(m):
        ans.append(abs(cd[j][0]-ab[i][0])+abs(cd[j][1]-ab[i][1]))
    ansn = ans.index(min(ans))+1
    print(ansn)

        

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

using namespace std;

int main(){

  int n, k;
  cin >> n >> k;
  vector<int> A(n);
  for(int i = 0; i < n; i++)cin >> A[i];
  vector<bool> dp(k + 1, false);

  for(int stones = 0; stones <= k; stones++){
    for(int x : A){
      if(stones >= x and !dp[stones - x])dp[stones] = true;
    }
  }
  string res = dp[k] == true ? "First" :  "Second";
  cout << res << endl;

  return 0;
}


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

typedef long long ll;
typedef pair<int, int> ii;

const int N = 301;
double dp[N][N][N];
int n;

double dfs(int a, int b, int c) {
  if (!a && !b && !c) return 0;
  if (dp[a][b][c] != 0) return dp[a][b][c];
  double abc = a + b + c;
  double exp = 1.0L * n / abc; // expectation t
  if (a > 0) exp += a / abc * dfs(a - 1, b, c);
  if (b > 0) exp += b / abc * dfs(a + 1, b - 1, c);
  if (c > 0) exp += c / abc * dfs(a, b + 1, c - 1);
  dp[a][b][c] = exp;
  return exp;
}

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

    int num, a = 0, b = 0, c = 0;
    cin >> n;

    for (int i = 0; i < n; ++i) {
      cin >> num;
      if (num == 1) ++a;
      else if (num == 2) ++b;
      else ++c;
    }

    double p = dfs(a, b, c);
    cout << setprecision(10) << fixed << p << endl;

    return 0;
}


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

using namespace std;

int main(){
    long N,M;
    long Ans = 0;
    cin >> N >> M;
    vector<pair<long, long> > Energy_Drink(N);
    for(long i = 0;i < N;i++){
        long a,b;
        cin >> a >> b;
        Energy_Drink[i] = make_pair(a,b);
    }
    sort(Energy_Drink.begin(),Energy_Drink.end());
    for(long i = 0;M > 0;i++){
        if(M < Energy_Drink[i].second){
            Ans += M * Energy_Drink[i].first;
            break;
        }
        M -= Energy_Drink[i].second;
        Ans += Energy_Drink[i].second * Energy_Drink[i].first;
    }
    cout << Ans << endl;
}


Measured memory_bytes: 1792
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse2")

#include<bits/stdc++.h>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;

#define int         long long
#define ll          long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define mp          make_pair
#define all(a)      (a).begin(),(a).end()
#define FF           first
#define SS           second
#define sz(x)       (int)x.size()
#define endl        '\n'
//#define hell          1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
// mp::cpp_int
//#define pp pair<pii,pii>
const int hell =1000000007;



int power(int a,int b)
{
  if(b==0)return 1;
  if(b==1)return a;
  int t=power(a,b/2);
  t%=hell;
  t*=t;
  t%=hell;
  if(b%2)return (t*a)%hell;
  else
     return t;
}

int gcd(int a,int b)
{
  if(b==0)return a;
  return gcd(b-a%b,a%b);
}

int digitsum(int x)
{
  while(x>9)
    {  int ans=0;
       while(x!=0)
       {
        ans+=x%10;
        x/=10;
       }
       x=ans;
    }
    return x;
}

int pw(int a,int b)
{
  int x=a;
  rep(i,1,b){a=a*x;}
  return a;
}




int solve( ){


int n;
cin>>n;
vi a(n);
int b[n+1]={0};
int c[n+1]={0};
int su=0;
int count=0,mn=hell;
rep(i,0,n){cin>>a[i];su+=abs(a[i]);
  if(a[i]<0){count++;}
  mn=min(mn,abs(a[i]));
}
if(count%2)
{
   su-=2*mn;
}
cout<<su;
return 0;
}

signed main()
{  int t=1;
 ios::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   cin.exceptions(cin.failbit);

    

 //sieve();
  clock_t time_req;

    // Without using pow function
    time_req = clock();
    
//cin>>t;

    int k=1;
   while(t--)
     {
       //cout<<"case #"<<k<<":"<<" ";k++;
      solve();
     }

         time_req = clock() - time_req;
 // cout << "Processor time taken is "
   // << (double)time_req/CLOCKS_PER_SEC << " seconds" << endl;


    return 0;
}


Measured memory_bytes: 2560
#include <stdio.h>
#include<math.h>
double hyo(int x,int h)
{
    double ans=x*x+x*sqrt(x*x+h*h*4);
    return ans;
}
int main(void)
{
    int x,h;
    while(1==1)
    {
        scanf("%d\n",&x);
        scanf("%d\n",&h);
        if(x==0&&h==0)break;
        printf("%f\n",hyo(x,h));
    }
    return 0;
}



Measured memory_bytes: 2044
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define pr pair<int,int>
#define mod 1000000007
#define endl "\n"

int power(int a,int b,int m=mod)
{
	if(b==0)	return 1;
	if(b==1)	return a;
	int res=power(a,b/2,m);
	res=(res*res)%m;
	if(b&1)	res=(res*a)%m;
	return res;
}

int modinv(int a){ return power(a,mod-2);}

void solve()
{
	int n,i;
	cin>>n;
	int a[n+1],cnt[n+1];
	memset(cnt,0,sizeof(cnt));
	for(i=2;i<=n;i++)
	{
		cin>>a[i];
		cnt[a[i]]++;
	}
	for(i=1;i<=n;i++)
		cout<<cnt[i]<<endl;
}

int32_t main()
{
	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	int t=1;//cin>>t;
	while(t--)	solve();
	return 0;
}

Measured memory_bytes: 6784
s = input()
t = input()

while s != '':
    if [i for i, x in enumerate(s) if x == s[0]] == [i for i, x in enumerate(t) if x == t[0]]:
        s = s.replace(s[0],'')
        t = t.replace(t[0],'')
    else:
        print('No')
        exit()

print('Yes')


Measured memory_bytes: 54332
#include <stdio.h>
#define N 350053
#define M 300007


int read()
{
	char c;
	while((c = getchar()) < 48 || c > 57);
	int x = c - 48;
	while((c = getchar()) > 47 && c < 58) x = x * 10 + c - 48;
	return x;
}

int ha[N] = {0};

int main() 
{
	int i, j, x, n, h, f = 1;
		
	n = read();
	for(i = 0; i < n; i++){
		x = read();
		if(!f) continue;
		h = x % M * 618 % M;
		for( ; ha[h] && ha[h] != x; h++);
		if(!ha[h]) ha[h] = x;
		else f = 0;
	}
	if(f) puts("YES");
	else puts("NO");
	
	return 0;
}

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

using namespace std;

#define DB( x ) cout << #x << " = " << x << endl;
#define LEFT(n) (2 * (n))
#define RIGHT(n) (2 * (n) + 1)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> node;
//typedef vector <vector <ll>> matrix;

const ll INF = 1e9;
const double EPS = 1e-9;
const ll MOD = (ll)(1000000007);
const ll MAXV = (ll)(1e5 - 100);
const ll MAXE = (ll)(1e6 + 10);


int main(){
	cin.sync_with_stdio( 0 );cin.tie( 0 );

	ll n;

	cin >> n;

	ll ans = 0;

	for(int i = 1;i <= n;i ++)
		if((ll)(log10((double)i) + 1LL) % 2LL == 1)
			ans ++;

	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 512
#include <algorithm>
#include <iostream>
#include <string>

#include <vector> 

#include <functional>
using namespace std;

int main()
{
    string s;
    cin >> s;
    int N = s.size();
    int ans,start,end;

    for (int i = 0; i < N;i++){
        if(s[i]=='A'){
            start = i;
            break;
        }
    }


    for (int j = N - 1; j >= 0;j--){
        if(s[j]=='Z'){
            end = j;
            break;
        }
    }


        cout << end - start + 1 << endl;
}


Measured memory_bytes: 3704
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>

using namespace std;

const long long MOD = 1000000007;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repn(i, n) for(int i = 1; i <= n; i++) 

int main(){
    int N, M; cin >> N >> M;
    int S[N+1], T[M+1];
    repn(i, N) cin >> S[i];
    repn(i, M) cin >> T[i];

    long long dp[N+2][M+2];
    rep(i, N+1) dp[i][0] = 0;
    rep(j, M+1) dp[0][j] = 0;
    repn(i, N) repn(j, M){
        if(S[i] == T[j])
            dp[i][j] = (dp[i-1][j] + dp[i][j-1] + 1 + MOD) % MOD;
        else
            dp[i][j] = (dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + MOD) % MOD;
    }
    cout << (dp[N][M]+1)%MOD << endl;
}


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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        String[] s = new String[k];
        for (int i = 0; i < k; i++) {
            s[i] = sc.next();
        }
        int y = n-1;
        boolean b = false;
        while(b == false) {
            y++;
            String str = Integer.toString(y);
            int d = 0;
            for (int i = 0; i < k; i++) {
                if (str.contains(s[i])) {
                    d++;
                }
            }
            if (d == 0) {
                b = true;
            }
        }
        System.out.println(y);
    }
}

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

#define ALL(c) (c).begin(), (c).end()
#define CALL(c) (c).cbegin(), (c).cend()
#define RALL(c) (c).rbegin(), (c).rend()
#define CRALL(c) (c).crbegin(), (c).crend()
#define REP(i, n) for (int i = 0; i < static_cast<int>(n); i++)
#define FOR(i, s, n) for (int i = s; i < static_cast<int>(n); i++)
#define PSORT(s,p,e) partial_sort((s), next((s), (p)), (e))
#define VIEW(v,t) for_each((v).begin(), (v).end(), [](t& a) { cout << a << " "; }); cout << endl;

const int INF = INT_MAX;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};

using PII = pair<int, int>;
using LL = long long;
using ULL = unsigned long long;
template<class T> using V = vector<T>;
template<class T> using V2 = vector<vector<T>>;
template<class T, int W=255> using A = array<T, W>;
template<class T, int W=255, int H=255> using A2 = array<array<T, W>, W>;

LL n;
V<LL> a;

LL calc(LL a, LL b) {
    if(a < b) swap(a,b);
    if(a % b == 0) return b;
    if(a % b == 1) return 1;
    return calc(b, a % b);
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cin >> n;
    REP(i,n) {
        LL x; cin >> x; a.push_back(x);
    }
    std::sort(ALL(a), [](LL& x, LL& y){ return x > y; });

    LL ans = a[0];
    FOR(i, 1, n) {
        ans = min(ans, calc(ans, a[i]));
    }
    cout << ans << "\n";
}

Measured memory_bytes: 1400
n = int(input())
ans = sum(list(range(1, n+1)))
n_3 = n//3
n_5 = n//5
n_15 = n//15
for i in range(1, n_3+1):
  ans -= i*3
for i in range(1, n_5+1):
  ans -= i*5
for i in range(1, n_15+1):
  ans += i*15
print(ans)

Measured memory_bytes: 48404
// Date: 2020-02-26

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

typedef long long LL;
typedef long double LD;
typedef vector<int> VI;
typedef pair<LL, LL> pll;
typedef pair<int, int> pii;
#define FIO ios::sync_with_stdio(false);cin.tie(0)
#define rep(i, a, b) for(int i = int(a); i <= int(b); ++i)
#define per(i, b, a) for(int i = int(b); i >= int(a); --i)
#define mem(x, y) memset(x, y, sizeof(x))
#define all(x) (x).begin(),(x).end()
#define mk make_pair
#define pb push_back
#define fi first
#define se second
const LL INF = 1e18;
const LL mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int N = 700 + 10;
template <typename T> void chkMax(T &x, T y) { x = max(x, y); }
template <typename T> void chkMin(T &x, T y) { x = min(x, y); }
LL qpow(LL x, LL y, LL MOD) {LL a=1; while(y){ if(y&1) a=a*x%MOD; x=x*x%MOD; y>>=1; } return a;}

int n, m;
int f[N][N], g[N][N], col[N], sz[N][2], tot;
bool flag;

void dfs(int u, int id) {
    sz[id][col[u]-1]++;
    rep(v, 1, n) if(!g[u][v]) {
        if(col[v]) {
            if(col[v] == col[u]) {
                flag = 0;
                return;
            }
        } else {
            col[v] = 3-col[u];
            dfs(v, id);
        }
    }
}

int solve() {
    f[0][0] = 1;
    rep(i, 1, tot) {
        rep(j, 0, n) {
            if(f[i-1][j]) f[i][j+sz[i][0]] = f[i][j+sz[i][1]] = 1;
        }
    }
    int ans = inf;
    rep(i, 0, n) {
        if(f[tot][i]) chkMin(ans, (i*(i-1)+(n-i)*(n-i-1))/2);
    }
    return ans;
}

int main() {
    scanf("%d%d", &n, &m);
    rep(i, 1, m) {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u][v] = g[v][u] = 1;
    }
    rep(i, 1, n) g[i][i] = 1;
    flag = 1;
    rep(i, 1, n) if(!col[i]) {
        ++tot;
        col[i] = 1, dfs(i, tot);
    }
    if(!flag) {
        puts("-1");
        return 0;
    }
    printf("%d\n", solve());
    

    return 0;
}

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

long long MOD = 1e9+7;
int MAX_INT = 1e9;

// 最大公約数
long long gcd(long long a, long long b){
  if(b == 0) return a;
  return gcd(b, a % b);
}
// 最小公倍数
long long lcm(long long a, long long b) {
  return a / gcd(a, b) * b;
}

// x^y%p
long long modpow(long long x, long long y, long long p=1) {
    long long res = 1;
    x = x % p;
    if (x == 0) return 0;
    while (y > 0) {
        if (y & 1) res = res * x % p;
        y = y>>1;
        x = x * x % p;
    }
    return res;
}

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

  long long N;
  cin >> N;
  long long ans = (modpow(10,N,MOD)+MOD - 2*modpow(9,N,MOD)+MOD+MOD + modpow(8,N,MOD)+MOD)%MOD;
  cout << ans%MOD << endl;

    return 0;
}


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

map< string, int > mp;

int main(){
     int i, j, k;
     int n;
     cin >> n;
     for(i=0; i<n; ++i){
          string str;
          cin >> str;
          mp[str]++;
     }
     cout << "AC x " << mp["AC"] << endl;
     cout << "WA x " << mp["WA"] << endl;
     cout << "TLE x " << mp["TLE"] << endl;
     cout << "RE x " << mp["RE"] << endl;
}


Measured memory_bytes: 3628
#include <iostream>
using namespace std;
const int maxn = 1e5 + 5;
const long long inf = 1e18;
typedef long long ll;
ll a[maxn];
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		if (a[i] == 0)
		{
			cout << 0 << endl;
			return 0;
		}
	}
	ll ans = 1;
	for (int i = 1; i <= n; i++)
	{
		if (a[i] > inf / ans)
		{
			cout << -1 << endl;
			return 0;
		}
		else
		{
			ans *= a[i];
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4368
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
using namespace std;
int main()
{
  int N;
  cin >> N;
  int sum = 0;
  vector<ll> a(N);
  rep(i, N)
  {
    cin >> a[i];
    while (a[i] % 2 == 0)
    {
      a[i] /= 2;
      sum++;
    }
  }
  cout << sum << endl;
  return 0;
}

Measured memory_bytes: 384
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

ll dp[225][225];

int main(void){
	int n,i,j;
	char c;
	cin >> n;
	dp[0][0] = 1ll;
	for(i=0; i<n; ++i){
		cin >> c;
		for(j=0; j<=n; ++j){
			if(c=='U'){
				add_mod(dp[i+1][j],dp[i][j]*j%MOD);
				if(j<n){
					add_mod(dp[i+1][j+1],dp[i][j]);
				}
			}else if(c=='D'){
				add_mod(dp[i+1][j],dp[i][j]*(j)%MOD);
				if(j>0){
					add_mod(dp[i+1][j-1],(dp[i][j]*(j)%MOD)*(j)%MOD);
				}
			}else{
				dp[i+1][j] = dp[i][j];
			}
		}
	}
	cout << dp[n][0] << endl;
	return 0;
}



Measured memory_bytes: 3452