akhauriyash/Code-Regression huggingface dataset:
#define _USE_MATH_DEFINES // M_PIなどの定義を使用するのに必要
#include <iostream>
#include <vector>
#include <string>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <climits>
#include <iomanip>
#include <deque>
#include <limits>

using namespace std;

const int64_t MOD = 1e9 + 7;

int main()
{
  int64_t N;
  int64_t K;

  cin >> N >> K;

  int64_t res_num = 0;
  for (int64_t k = K; k <= N + 1; k++) {
    int64_t small = k * (k - 1) / 2;
    int64_t big = k * (2 * N - k + 1) / 2;
    res_num += big - (small - 1);
    res_num %= MOD;
  }

  cout << res_num << endl;

  return 0;
}


Measured memory_bytes: 3636
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;

namespace AtTest.ABC_172
{
    class D
    {
        static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(OpenStandardOutput()) { AutoFlush = false };
            SetOut(sw);

            Method(args);

            Out.Flush();
        }

        static void Method(string[] args)
        {
            long n = ReadLong();

            long res = 0;
            for(long i = 1; i <= n; i++)
            {
                long cnt = n / i;
                res += i * cnt * (cnt + 1) / 2;
            }

            WriteLine(res);
        }

        private static string Read() { return ReadLine(); }
        private static char[] ReadChars() { return Array.ConvertAll(Read().Split(), a => a[0]); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
    }
}


Measured memory_bytes: 27516
#include<stdio.h>
int main(void){
  int N, i;
  scanf("%d", &N);
  char S[N + 1];
  int p = 0;
  int w = 0;
  int g = 0;
  int y = 0;
  do{
    for(i = 0; i < N; i++){
      scanf("%s", &S[i]);
      if(S[i] == 'P')
        p = 1;
      else if(S[i] == 'W')
        w = 1;
      else if(S[i] == 'G')
        g = 1;
      else if(S[i] == 'Y')
        y = 1;
      }
    }while(p < 1 && w < 1 && g < 1);
  if(y > 0)
  printf("Four");
  else
  printf("Three");
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
//cervello|Phoenix
using namespace std;
#define ll long long int
#define eb emplace_back
#define mk make_pair
#define pr pair<int,int>
#define all(x) x.begin(),x.end()
#define mod 1000000007

int main(){
  ios_base::sync_with_stdio(false);
    // #ifndef ONLINE_JUDGE
    //   freopen("input.txt", "r", stdin);
    //   freopen("output.txt", "w", stdout);
    // #endif
  double r; cin>>r;
  double v1=22,v2=7;
  double pi=(v1/v2);
  r=2*(pi)*r;
  cout<<fixed<<setprecision(12)<<r<<"\n";
  return 0;
}

Measured memory_bytes: 3800
import java.util.*;

class Main {
    public static void main(String args[]) {
        Scanner inp = new Scanner(System.in);
        do_(inp);
        inp.close();
    }
    public static void do_(Scanner inp) {
        int a = inp.nextInt();
        // int b = inp.nextInt();
        System.out.println((int)Math.ceil(a / 2.0));
    }
}


Measured memory_bytes: 23124
/*
 * FileName:     longest_common_subsequence
 * CreatedDate:  2020-05-24 20:52:51 +0900
 * LastModified: 2020-05-24 21:11:23 +0900
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define str_max 1001
int dp[str_max][str_max];
int max(int s,int t){
    if(s<t){return t;}
    return s;
}
int three_max(int a,int b,int c){
    int s = max(a,b);
    return max(s,c);
}
int main(void){
    int q;
    scanf("%d",&q);
    for(int i=0;i<q;i++){
        memset(dp,0,sizeof(dp));
        char *x = malloc(str_max*sizeof(char));
        char *y = malloc(str_max*sizeof(char));
        scanf("%s",x);
        scanf("%s",y);
        for(int i=1;i<strlen(x)+1;i++){
            for(int j=1;j<strlen(y)+1;j++){
                if(x[i-1]==y[j-1]){
                    dp[i][j]=three_max(dp[i-1][j-1]+1,dp[i-1][j],dp[i][j-1]);
                }
                else{
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        printf("%d\n",dp[strlen(x)][strlen(y)]);
        free(x);
        free(y);
    }
    return 0;
}



Measured memory_bytes: 5708
import sys

N = input()
S = input()
size = len(S)

if N != str(size):
 print("不正な入力です。")
 sys.exit()

max = 0
temp = 0

for i in range(size):
 if S[i] == "I":
  temp += 1
 elif S[i] == "D":
  temp -= 1
 else:
  print("I,D以外の文字が含まれています。")
  sys.exit()
 
 if max < temp:
  max = temp

print(max)

Measured memory_bytes: 3064
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <math.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<n;++i)
#define rep1(i,n) for(ll i=1;i<n;++i)
#define mrep(i,n) for(ll i=n;i>=0;--i)
#define vl vector<ll>
#define vvl vector<vector<ll> >
#define vb vector<bool>
#define vvb vector<vector<bool> >
#define inf 1001001001001000
#define mod 1000000007
#define pi 3.1415926535
using namespace std;

//abs(a-b)<c<a+b
//c<a+b
//b<c
ll binary_search1(vl &a,ll key,ll key2){
    
}

int main(void){
    ll n;
    cin>>n;
    vl l(n);
    rep(i,n) cin>>l[i];
    sort(l.begin(),l.end());
    ll ans = 0;
    rep(i,n) for(ll j=i+1;j<n;++j){
        ll c = (lower_bound(l.begin(),l.end(),l[i]+l[j])-l.begin());
        c--;
        
        if(c<=j) continue;
        else ans += c-j;
    }
    cout<<ans<<endl;
}

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

using namespace std;

int main() {
    long long int n, k;
    scanf("%lld %lld", &n, &k);
    n=n%k;
    if(n<(k+1)/2)
        printf("%lld", n);
    else
        printf("%lld", k-n);
    
    
    
    
    return 0;
}

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

using i8  = int8_t;   /* -128 ~ 127 */
using u8  = uint8_t;  /* 0 ~ 255 */
using i16 = int16_t;  /* -32,768 ~ 32,767 */
using u16 = uint16_t; /* 0 ~ 65,535 */
using i32 = int32_t;  /* -2,147,483,648 ~ 2,147,483,647 */
using u32 = uint32_t; /* 0 ~ 4,294,967,295 */
using i64 = int64_t;  /* -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 */
using u64 = uint64_t; /* 0 ~ 18,446,744,073,709,551,615 */
using f32 = float;    /* (-3.4 * 10^38) ~ (3.4 * 10^38) */
using f64 = double;   /* (-1.7 * 10^308) ~ (1.7 * 10^308) */
using f80 = __float80;
template <class T> using Vec = vector<T>;
constexpr i64 INF = 1010000000000000017;
constexpr i64 MOD = 1e9 + 7;
constexpr f64 EPS = 1e-12;
constexpr f64 PI = 3.14159265358979323846;
#define ALL(v) v.begin(), v.end()
#define GCD(a, b) __gcd(a, b) /* 最大公約数 */
#define LCM(a, b) a / __gcd(a, b) * b /* 最小公倍数 */

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}

void Main() {
    string S, T;
    cin >> S;
    cin >> T;
    bool res = true;
    for (int i = 0; i < S.size(); i++) {
        if (S[i] != T[i]) res = false;
    }
    string result = res? "Yes" : "No";
    cout << result << endl;

}


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

int main() {
  int k;
  string s;
  cin >> k >> s;
  if(s.size() <= k){cout << s << endl;return 0;}
  else{
    for(int i=0;i<k;i++){
      cout << s[i];
    }
  }
  cout << "..." << endl;
}


Measured memory_bytes: 3628
# include <bits/stdc++.h>
# define INF 1e9
using namespace std;

int main(){

  int N;
  cin >> N;
  int a[N];
  int count2 = 0;
  for(int i=0; i <N; ++i){
    cin >> a[i];
    while(a[i] % 2 == 0){
      count2++;
      a[i] = a[i] / 2;
    }
  }
  cout << count2 << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, s, n) for(int i = s; i < (int)n; i++)
#define per(i, n) for(int i = n; i >= 0; i--)
#define ROF(i, s, n) for(int i = s; i >= (int)n; i--)
#define FORIT(i, A) for (auto i : A)
#define PRINT(x) cout << (x) << "\n"
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MP make_pair
#define EACH(i, n) for (__typeof((n).begin()) i = (n).begin(); i != (n).end(); ++i)
#define SZ(a) int((a).size())
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define CLR(a) memset((a), 0 ,sizeof(a))
#define NCLR(a) memset((a), -1 ,sizeof(a))
#define dump(x) cout << #x << " = " << (x) << "\n";
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << "\n";
#define sq(n) (n) * (n)
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef priority_queue<int> maxpq;
typedef priority_queue< int, vector<int>, greater<int> > minpq;
typedef complex<double> P;
static const double EPS = 1e-10;
static const double PI = acos( -1.0 );
static const int mod = 1000000007;
static const int INF = 1 << 29;
static const LL LL_INF = 1152921504606846976;
static const int dx[] = { -1, 0, 1, 0, 1, -1, 1, -1 };
static const int dy[] = { 0, -1, 0, 1, 1, 1, -1, -1 };

int dp[ 4 ][ 32768 ];

int main() {
	int ans = 0;
	string s;
	cin >> s;
	int i = 0;
	while ( s.size() != i ) {
		int _j = 0, _o = 0, _i = 0;
		while ( s.size() != i && s[ i ] == 'J' ) {
			_j++;
			i++;
		}
		while ( s.size() != i && s[ i ] == 'O' ) {
			_o++;
			i++;
		}
		while ( s.size() != i && s[ i ] == 'I' ) {
			_i++;
			i++;
		}
		if ( _o <= _j && _o <= _i ) {
			ans = max( _o, ans );
		}
	}
	printf( "%d\n", ans );
	return 0;
}

Measured memory_bytes: 2048
H, W = map(int, input().split())
grid = [input() for _ in range(H)]
dp = [[float('inf')] * W for i in range(H)]
dp[0][0] = 1 if grid[0][0] == '#' else 0

for i in range(H):
    for j in range(W):
        for y, x in ((1,0), (0,1)):
            ni, nj = i + y, j + x
            if ni >= H or nj >= W:
                continue
            c = 0
            if grid[ni][nj] == '#' and grid[i][j] == '.':
                c = 1
            dp[ni][nj] = min(dp[ni][nj], dp[i][j] + c)

print(dp[H-1][W-1])

Measured memory_bytes: 41456
#include<bits/stdc++.h>
using namespace std;
 
typedef long long int ll;
#define mamba() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 
int main()
{
	mamba()
    ll n,a,b;cin>>n>>b>>a;
  	cout<<(n/(a+b))*b+(min(n%(a+b),b));
}

Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author tatsumack
 */

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001001ll
#define fcout cout << fixed << setprecision(12)

using namespace std;

typedef pair<int, int> P;

class ATheNumberOfEvenPairs {
public:
    void solve(std::istream& cin, std::ostream& cout) {
        int N, M;
        cin >> N >> M;
        int res = 0;
        if (N >= 2) res += N * (N-1) / 2;
        if (M >= 2) res += M * (M-1) / 2;
        cout << res << endl;
    }
};


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    std::istream& in(std::cin);
    std::ostream& out(std::cout);

    ATheNumberOfEvenPairs solver;
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(){
  int a,b;
  scanf("%d %d", &a, &b);
  if (a<b){
    printf("a < b\n");
  } else if (a>b){
    printf("a > b\n");
  } else if(a==b){
    printf("a == b\n");
  }
  return 0;
}

Measured memory_bytes: 1712
#include<stdio.h>
int main(){
    int n,a,b,t;
    scanf("%d %d %d",&n,&a,&b);
    t=n*a;
    if(t<=b){
        printf("%d\n",t);
    }
    else{
        printf("%d\n",b);
    }
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define PB push_back
using namespace std;



const int N=1e5+100;
vector <int> x[N];
int vor[N];
vector <int>jj[N];
vector <int> s;
int mark[N];
int ll=0;
int mn[N];
int jk=0;
vector <int>tp;

int dp[N];



int BFS(){
    int h=0;

    while (s.size()){
        int k=s.back();
        tp.push_back(k);
        jk++;
        s.pop_back();
        int mj=0;
        for (int e : x[k]){

            h++;
            vor[e]--;
            if (vor[e]==0){
                mj++;
                s.PB(e);
            }

        }
    }

}
int main(){
    int n,m,u,v;
    cin >> n >> m;
    for (int i=0 ; i<m ; i++){
        cin >> u >> v;
        u--;
        v--;
        jj[v].PB(u);

        x[u].PB(v);
        vor[v]++;
    }
    for(int i=0 ; i<n ; i++){
        if (vor[i]==0){
            s.PB(i);
        }
    }

    BFS();
    for (int q:tp) {
        //cout << q << ": ";
        int maxi = 0;
        for (w : jj[q]){
            //cout << w << " ";
            maxi=max(dp[w]+1,maxi);
        }
        //cout << "\n";
        dp[q]=maxi;


    }
    int ee=0;
    for (int i=0 ; i<n ; i++){
       // cout << dp[i] << " ";
        ee=max(ee,dp[i]);


    }
    cout << ee;
    //cout << jk;

}


Measured memory_bytes: 12540
n,k = map(int,input().split())
x = list(map(int,input().split()))
ans = 10 ** 12
for i in range(n-k+1):
    ans = min(ans,abs(x[i])+(abs(x[i+k-1]-x[i])),abs(x[i+k-1])+(abs(x[i+k-1]-x[i])))
print(ans)


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

int main() {
  int h, w, n, c = 0;
  cin >> h >> w >> n;
  vector<int> a(n);
  vector<vector<int>> out(h, vector<int>(w));
  for(int i = 0; i < n; i++)
    cin >> a.at(i);
  for(int i = 0; i < h; i++) {
    if(i % 2) {
      for(int j = w - 1; j >= 0; j--) {
        if(a.at(c) == 0)
          c++;
        out.at(i).at(j) = c + 1;
        a.at(c)--;
      }
    } else {
      for(int j = 0; j < w; j++) {
        if(a.at(c) == 0)
          c++;
        out.at(i).at(j) = c + 1;
        a.at(c)--;
      }
    }
  }
  for(int i = 0; i < h; i++) {
    for(int j = 0; j < w; j++) {
      if(j != w - 1)
        cout << out.at(i).at(j) << " ";
      else
        cout << out.at(i).at(j) << endl;
    }
  }
}

Measured memory_bytes: 384
import java.util.Scanner;

public class Main {
    public boolean search(int[] s, int n, int key) {
        int i = 0;
        s[n] = key;
        while (s[i] != key) i++;
        return i != n;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] s = new int[n + 1];
        for (int i = 0; i < n; i++) {
            s[i] = in.nextInt();
        }

        int q = in.nextInt();
        int[] t = new int[q];

        Main test = new Main();
        int sum = 0;

        for (int i = 0; i < q; i++) {
            int key = in.nextInt();
            if(test.search(s, n, key)) sum++;
        }
        System.out.println(sum);
    }
}


Measured memory_bytes: 40624
#abc079 train ticket
s = input()
for bit in range(1<<3):
    a = int(s[0])
    func = s[0]
    for i in range(3):
        if bit & (1<<i):
            func += '+'
            a += int(s[i+1])
        else : #もし1というフラグが立っていなければ、引くというプログラム
            func += '-'
            a -= int(s[i+1])
        func += s[i+1]
    
    if a == 7:
        print(func + '=7')
        exit()
print('No')
        


Measured memory_bytes: 9180
H, W = map(int, input().split())
S = [list(input()) for i in range(H)]

check_i = []
check_j = []
for i in range(H):
    if H == 1:
        check_i = [0]
    elif i == 0:
        check_i = [0, 1]
    elif i == H-1:
        check_i = [i-1, i]
    else:
        check_i = [i-1, i, i+1]
    for j in range(W):
        if S[i][j] == "#":
            continue

        if W == 1:
            check_j = [0]
        elif j == 0:
            check_j = [0, 1]
        elif j == W-1:
            check_j = [j-1, j]
        else:
            check_j = [j-1, j, j+1]
        
        count = 0
        for k in check_i:
            for l in check_j:
                if S[k][l] == "#":
                    count += 1
        S[i][j] = str(count)

for i in range(H):
    print("".join(S[i]))

Measured memory_bytes: 3188
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>
#include <set>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <stack>
#include <map>
#define REP(i, n) for(int i=0; i<n; i++)
#define REPR(i, n) for(int i=n; i>0; i--)
#define FOR(i, m, n) for(int i=m; i<n; i++)
#define FORR(i, m, n) for(int i=m; i>=n; i--)
#define INF 1999999999
#define VSORT(v) sort(v.begin(), v.end())
#define pb(a) push_back(a)
using namespace std;
typedef long long ll;

#ifdef INPUT
stringstream input(R"(
12
757232153 372327760 440075441 195848680 354974235 458054863 463477172 740174259 615762794 632963102 529866931 64991604
74164189 98239366 465611891 362739947 147060907 118867039 63189252 78303147 501410831 110823640 122948912 572905212
)");
#define cin input
#endif

int main()
{
    int n;
    cin >> n;
    int ans = 0;
    ll sum = 0;
    ll subsum = 0;
    int flag = 0;

    vector <ll> a(n);
    vector <ll> b(n);
    vector <ll> diff(n);
    for (int i=0; i<n; i++)
        cin >> a[i];
    for (int i=0; i<n; i++)
        cin >> b[i];
    for (int i=0; i<n; i++)
    {
        diff[i] = a[i]-b[i];
        sum += diff[i];
        if (diff[i] < 0)
        {
            subsum += diff[i];
            flag = 1;
        }
    }

    if (flag == 0)
        ans = 0;
    else if (sum < 0)
        ans = -1;
    else
    {
        sort(diff.begin(), diff.end(), greater<ll>());
        for (int i=0; i<n; i++)
        {
            if (diff[i] > 0)
            {
                if (subsum >= 0)
                    continue;
                subsum += diff[i];
                ans += 1;
            }
            else if (diff[i] < 0)
                ans += 1;
        }
    }

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

Measured memory_bytes: 2560
#include <stdio.h>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <iostream>
#include<math.h>
#include<bitset>
#include<iomanip>
#include<queue>
using namespace std;

int main() {
	int N, M; cin >> N >> M;
	vector<long long> A(N);
	vector<pair<long long,int>> B(M);
	for (int i = 0; i < N; i++)cin >> A[i];
	for (int i = 0; i < M; i++)cin >> B[i].second >> B[i].first;
	sort(A.begin(), A.end());
	sort(B.begin(), B.end());
	int c = M-1, z = 0;
	for (int i = 0; i<N ; i++) {

		if (A[i] < B[c].first) {
			A[i] = B[c].first; z++;
		}
		if (z == B[c].second) { z = 0; c--; }
		if (c < 0)break;
	}
	long long ans = 0;
	for (int i = 0; i < N; i++)ans += A[i];
	cout << ans << endl;
}



Measured memory_bytes: 2560
# -*- coding: utf-8 -*-


def maximum_profit(profits):
    max_v = profits[1] - profits[0]
    min_v = profits[0]

    for j in range(1, len(profits)):
        max_v = max(max_v, profits[j]-min_v)
        min_v = min(min_v, profits[j])

    print(max_v)


def to_int(v):
    return int(v)


if __name__ == '__main__':
    l = to_int(input())
    profits = [to_int(input()) for i in range(l)]

    maximum_profit(profits)

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

int main() {
  
  int n;
  cin >> n;
  
  int a,saishou = 0;
  vector<int> c(9,0);
  
  for ( int i = 0; i < n; i++){
    cin >> a;
    if ( a < 400 ){
      c[0] = 1;
    }else if ( a >= 400 && a < 800 ){
      c[1] = 1;
    }else if ( a >= 800 && a < 1200 ){
      c[2] = 1;
    }else if ( a >= 1200 && a < 1600 ){
      c[3] = 1;
    }else if ( a >= 1600 && a < 2000 ){
      c[4] = 1;
    }else if ( a >= 2000 && a < 2400 ){
      c[5] = 1;
    }else if ( a >= 2400 && a < 2800 ){
      c[6] = 1;
    }else if ( a >= 2800 && a < 3200 ){
      c[7] = 1;
    }else{
      c[8]++;
    }
  }
  
  for ( int i = 0; i < 8; i++){
    saishou += c[i];
  }
  
  if ( saishou == 0 ){
    cout << 1 << ' ' << c[8] << endl;
  }else{
    cout << saishou << ' ' << saishou + c[8] << endl;
  }
  
}


Measured memory_bytes: 3572
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] lines = br.readLine().split(" ");
        int n = Integer.parseInt(lines[0]);
        int m = Integer.parseInt(lines[1]);
        int[][] vector1 = new int[n][m];
        for (int i = 0; i < n; i++) {
            lines = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                vector1[i][j] = Integer.parseInt(lines[j]);
            }
        }
        int[] vector2 = new int[m];
        for (int i = 0; i < m; i++) {
            vector2[i] = Integer.parseInt(br.readLine());
        }
        for(int i=0;i<n;i++){
            int sum=0;
            for(int j=0;j<m;j++){
                sum+=vector1[i][j]*vector2[j];
            }
            System.out.println(sum);
        }

    }
}

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

#define FORE(i, a) for (auto i = a.begin(); i != a.end(); ++i)
#define REPU(i, a, b) for (int i = (a); i < (b); ++i)
#define REPD(i, a, b) for (int i = (a); i > (b); --i)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())

vector<string> split(const string &s, char c) {
	vector<string> v; stringstream ss(s); string x;
	while (getline(ss, x, c)) v.push_back(x);
	return v;
}
#define DEBUG(args...) { vector<string> _v = split(#args, ','); err(_v.begin(), args); }
void err(vector<string>::iterator it) {}
template<typename T, typename... Args>
void err(vector<string>::iterator it, T a, Args... args) {
	cerr << "[DEBUG] " << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << '\n';
	err(++it, args...);
}

typedef long long ll;
const int MOD = 1000000007;

template<class T, class U> inline T tmin(T a, U b) { return (a < b) ? a : b; }
template<class T, class U> inline T tmax(T a, U b) { return (a > b) ? a : b; }
template<class T, class U> inline void amax(T &a, U b) { if (b > a) a = b; }
template<class T, class U> inline void amin(T &a, U b) { if (b < a) a = b; }
template<class T> T gcd(T a, T b) { while (b != 0) { T c = a; a = b; b = c % b; } return a; }

const int N = 100005;
vector<int> g[N];

int solve(int v) {
	int ans = 0, cnt = 0;
	vector<int> rk;
	for (int u : g[v]) {
		rk.push_back(solve(u));
	}
	if (!rk.empty()) {
		sort(ALL(rk));
		reverse(ALL(rk));
		REPU(i, 0, rk.size()) {
			amax(ans, rk[i] + i + 1);
		}
	}
	return ans;
}

int main(int argc, char *argv[]) {
	ios_base::sync_with_stdio(false);

	int n; cin >> n;
	REPU(i, 2, n + 1) {
		int a; cin >> a;
		g[a].push_back(i);
	}
	cout << solve(1) << endl;
	
	return 0;
}


Measured memory_bytes: 13568
def pre_combi1(n, p):
    fact = [1]*(n+1)  # fact[n] = (n! mod p)
    factinv = [1]*(n+1)  # factinv[n] = ((n!)^(-1) mod p)
    inv = [0]*(n+1)  # factinv 計算用
    inv[1] = 1
    # 前処理
    for i in range(2, n + 1):
        fact[i]= fact[i-1] * i % p
        inv[i]= -inv[p % i] * (p // i) % p
        factinv[i]= factinv[i-1] * inv[i] % p
    return fact, factinv

def combi1(n, r, p, fact, factinv):
    """
    k<n<10**7でpが素数のときのnCr % pを求める
    """
    # 本処理
    if r < 0 or n < r:
        return 0
    r = min(r, n-r)
    return fact[n] * factinv[r] * factinv[n-r] % p

n,k=map(int,input().split())
f,inv=pre_combi1(2005,10**9+7)
for i in range(1,k+1):
  print(combi1(n-k+1,i,10**9+7,f,inv)*combi1(k-1,i-1,10**9+7,f,inv)%(10**9+7))



Measured memory_bytes: 9340
import java.util.*;

public class Main {
	public static void main(String args[]) {
      	Scanner sc = new Scanner(System.in);
      	String S = sc.nextLine();
      	if (YesNo(S)) {
          Yes();
        } else {
          No();
        }
    }
  	public static boolean YesNo(String S) {
      if ((S.length() % 2) != 0) {
        return false;
      }
      for (int i = 0; i < S.length(); i += 2 ) {
        if (S.substring(i,i+1).equals("h") && S.substring(i+1,i+2).equals("i")) {
          continue;
        }
        return false;
      }
      return true;
    }
    public static void Yes() {
      	System.out.println("Yes");
    }
	public static void No() {
		System.out.println("No");
    }
}

Measured memory_bytes: 23636
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c;
    cin>>a>>b;
    c=b-a+1;
    int i;
    for(i=1;i<=a;i++)
    {
        cout<<c<<" ";
        c++;
    }
    for(i=1;i<a;i++)
    {
        cout<<c<<" ";
        c++;
    }
    return 0;
}


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

using namespace std;

const int N = 1e5 + 5;

vector<bool> prime;

void sieve() {
   prime.resize(N , true);
   prime[0] = prime[1] = false;
   for (int i = 2; i <= N; i++) {
      if (prime[i]) {
         if (i * 1LL * i <= N) {
            for (int j = i * i; j <= N; j += i) {
               prime[j] = false;
            }
         }
      }
   }
}

int main() {
   ios_base :: sync_with_stdio(0);
   cin.tie(0) , cout.tie(0);
   int n;
   cin >> n;
   sieve();
   while (!prime[n])
      n++;
   cout << n << '\n';
   return 0;
}


Measured memory_bytes: 256
import java.util.*;
import java.io.*;
public class Main{
/// functions
static long gcd(long a,long b){if(b==0){return a;}return gcd(b,a%b);}
static long Modpow(long a,long p,long m){if(p==1){return a;}long x=Modpow(a,p/2,m);x=(x*x)%m;return (p&1l)!=0? (x*a)%m:x;}
static long Modmul(long a,long b,long m){return ((a%m)*(b%m))%m;}
static long ModInv(long a,long m){return Modpow(a,m-2,m);}
static long nck(int n,int r,long m){if(r>n){return 0l;}return Modmul(f[n],ModInv(Modmul(f[n-r],f[r],m),m),m);}
// end
static long[] f;

public static void main(String[] args) throws FileNotFoundException, IOException{
       Scanner s=new Scanner(System.in);
       StringBuilder sb=new StringBuilder();
       BufferedWriter out=new BufferedWriter(new OutputStreamWriter(System.out));
       int h=s.nextInt(),n=s.nextInt();
       int[][] arr=new int[n+1][2];
       for(int i=1;i<=n;i++){
       	arr[i][0]=s.nextInt();arr[i][1]=s.nextInt();
       }
       int[][] dp=new int[h+1][n+1];
       for(int i=1;i<=h;i++){dp[i][0]=Integer.MAX_VALUE;}
       
       for(int i=1;i<=h;i++){
       	for(int j=1;j<=n;j++){
       		if(i<arr[j][0]){dp[i][j]=Math.min(arr[j][1],dp[i][j-1]);}
       		else{
       			dp[i][j]=Math.min(dp[i][j-1],dp[i-arr[j][0]][j]+arr[j][1]);
       		}
       	}
       }
        out.write(dp[h][n]+"");
        out.flush();
  }
}


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

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

  vector<string> vec(N);
  for (int i = 0; i < N; i++) {
   cin >> vec.at(i);
  }

  sort(vec.begin(), vec.end());
  vector<int> vcount(N);
  int count=0;
  int maxcount=0;
  for (int i = 0; i < N; i++) {
   if (i==0){
     count+=0;
   }
   else{
     if(vec.at(i-1)==vec.at(i)){
       count+=1;
       if (i==N-1) maxcount=max(count,maxcount);
     }
     else{
       maxcount=max(count,maxcount);
       count=0;
     }
   }
   vcount.at(i)=count;
  }

  for (int i = 0; i < N; i++) {
   if (vcount.at(i)==maxcount) cout << vec.at(i)<< endl;
  }
}

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

list<int> li;

void insert(int x) { li.push_front(x); }
void deleteX(int x) {
  for (auto it = li.begin(); it != li.end(); ++it) {
    if (*it == x) {
      it = li.erase(it);
      break;
    }
  }
}
void deleteFirst() { li.pop_front(); }
void deleteLast() { li.pop_back(); }

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    char command[11];
    int x;
    scanf("%s", &command);
    if (command[0] == 'i') {
      scanf("%d", &x);
      insert(x);
    } else if (command[6] == 'F') {
      deleteFirst();
    } else if (command[6] == 'L') {
      deleteLast();
    } else {
      scanf("%d", &x);
      deleteX(x);
    }
  }
  for (auto it = li.begin(); it != li.end();) {
    printf("%d", *it);
    ++it;
    if (it != li.end()) {
      printf(" ");
    }
  }
  printf("\n");
  return 0;
}



Measured memory_bytes: 34360
N = int(input())
A = list(map(int, input().split()))
f = 1
for i in range(N):
  if A[i] % 2 == 0:
    if (A[i] % 3 != 0) and (A[i] % 5 != 0):
      f = 0
if f == 0:
  print("DENIED")
else:
  print("APPROVED")



Measured memory_bytes: 2940
/*****************Bismillahir Rahmanir Rahim***********************/

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

/************************Start Of Template*************************/

/******** Mahin Shefat - GhOstMan *************/


#define     pb              push_back
#define     popb            pop_back
#define     ll              long long int
#define     ull             unsigned long long int
#define     max3(a,b,c)     max(a,max(b,c))
#define     max4(a,b,c,d)   max(max3(a,b,c),d)
#define     min3(a,b,c)     min(a,min(b,c))
#define     min4(a,b,c,d)   min(a,min3(b,c,d))
#define     MOD             1000000007
#define     f               first
#define     s               second
#define     mem(a,v)        memset(a,v,sizeof(a))
#define     mp              make_pair
#define     check           printf("check")
#define     sqr(x)          (x)*(x)
#define     all(v)          v.begin(),v.end()
#define     fast            ios_base::sync_with_stdio(0);cin.tie(0)
#define     pii             pair<int,int>
#define     Pair            pair<ll,ll>
#define     MAX             1000000000000014
#define     MIN             -1000000000000014
#define     endl            '\n'
#define     Fread           freopen("inputdur.txt","r",stdin)
#define     Fwrite          freopen("output.txt","w",stdout)

/************************End Of Template*************************/
string st[100005];
set < string > ss;
map < string , int > Map;
int main(){
	fast;
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> st[i];
		sort(all(st[i]));
		ss.insert(st[i]);
		Map[st[i]]++;
	}	
	ll ans = 0;	
	for(auto x : ss){
		ll cnt = Map[x];
		ans += ((ll)cnt * (cnt - 1)) / 2;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 25984
N,W=map(int,input().split())
weight=[0]*N
value=[0]*N
for i in range(N):
    value[i],weight[i]=map(int,input().split())
dp=[[0 for i in range(W+1)] for j in range(N+1)]
for i in range(W+1):
    dp[0][i]=0

for i in range(N):
    for w in range(W+1):
        if weight[i]<=w:
            dp[i+1][w]=max(dp[i][w-weight[i]]+value[i], dp[i][w])
        else:
            dp[i+1][w]=dp[i][w]
print(dp[N][W])



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

static const int MAX = 200000;

int main(){
  int R[MAX], n;

  cin >> n;
  for(int i = 0; i < n; i++) cin >> R[i];

  int maxProfit = numeric_limits<int>::min();
  int minv = R[0];

  for(int i = 1; i < n; i++)
  {
    maxProfit = max(maxProfit, R[i] - minv);
    minv = min(minv, R[i]);
  }

  cout << maxProfit << endl;

  return 0;
}


Measured memory_bytes: 3884
r, c = gets.split.map(&:to_i)
rows = r.times.map { gets.split.map(&:to_i) }

rows.each do |row|
  print row.join(' ')
  print ' ', row.inject(:+), "\n"
end

sums = c.times.map { |i| rows.map {|row| row[i] }.inject(:+) }
print sums.join(' ')
print ' ', sums.inject(:+), "\n"

Measured memory_bytes: 6140
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    S,T=ST().split()
    print(T,S,sep="")
if __name__ == '__main__':
    main()

Measured memory_bytes: 3700
from sys import stdin


def dfs(e, ans, graph, done, N):
    if sum(done) == N:
        ans += 1
        return ans
    for s in graph[e]:
        if not done[s]:
            done[s] = True
            ans = dfs(s, ans, graph, done, N)
            done[s] = False
    return ans


def main():
    lines = stdin.readlines()
    N, M = map(int, lines[0].split())
    graph = [[] for i in range(N)]
    for i in range(1, M + 1):
        a, b = map(int, lines[i].split())
        # 0-based indexing
        graph[a - 1].append(b - 1)
        graph[b - 1].append(a - 1)
    ans = 0
    done = [False] * N
    done[0] = True
    print(dfs(0, ans, graph, done, N))
    return


main()


Measured memory_bytes: 3064
#include <stdio.h>

#define MAX(A,B) \
  ( (A) > (B) ? (A) : (B) )

/** Application main entry point. */
int main (
  int     argc,
  char  * argv[ ]
  )
{
  int i, j;

  for ( ; ; )
  {
    int res = 0;
    int ti, tj;
    int n;

    scanf ( "%d", &n );
    if ( !( n ) ) break ;

    for ( j = 0; ( tj = j * j * j ) <= n; ++j )
    for ( i = 0; ( ti = i * ( i + 1 ) * ( i + 2 ) / 6 + tj ) <= n; ++i )
    {
      res = MAX( res, ti );
    }

    printf ( "%d\n", res );
  }

  return ( 0 );
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
 
#define vi vector<int>
#define ll long long
#define vvi vector<vi>
#define vll vector<ll>
#define vvll vector<vll>
#define MOD 1000000007
#define endL << '\n'
#define ii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define mp make_pair
#define endL << '\n'
#define vii vector<ii>
#define pb push_back

/*const int N = 1000000;
int lp[N+1];
vector<ll> pr;

void sieve(){
	for (int i=2; i<=N; ++i) {
	    if (lp[i] == 0) {
	        lp[i] = i;
	        pr.push_back (i);
	    }
	    for (int j=0; j<(int)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
	        lp[i * pr[j]] = pr[j];
	}
}*/

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int t=1; //cin >> t;
	while(t--){
		int n; cin >> n;
		string s;
		vii noneg, neg;
		int bal, mbal, sum = 0;
		for (int i = 0; i < n; i++){
			cin >> s;
			mbal = 0, bal = 0;
			for (char c : s){
				if (c == '(') bal++;
				else bal--;
				mbal = min(mbal, bal);
			}
			sum += bal;
			if (bal >= 0) noneg.pb(mp(mbal, bal));
			else neg.pb(mp(-mbal + bal, bal));
		}
		if (sum != 0) {cout << "No" endL; return 0;}
		int curr = 0;
		sort(noneg.rbegin(), noneg.rend());
		sort(neg.rbegin(), neg.rend());
		//for (ii par : noneg) cout << par.fi << "-" << par.se << " "; cout endL;
		bool flag = true;
		for (ii par : noneg){
			if (par.fi + curr >= 0){
				curr += par.se;
			}
			else flag = false;
		}
		for (ii par : neg){
			if (par.se - par.fi + curr >= 0) curr += par.se;
			else flag = false;
		}
		if (flag) cout << "Yes" endL;
		else cout << "No" endL;
	}	
}

Measured memory_bytes: 11304
import math
import sys
import numpy as np
import collections

#n, a, b= map(int, input().split())
n, y  = map(int, input().split())
#s = list(str(input()))
#n = int(input())

max1 = int(y/1000) + 1

for i in range(max1):
  rest = y-i*9000-n*1000
  mod = rest%4000
  ii  = int((rest)/4000)
  iii = n-i-ii
  if(mod == 0 and iii>=0 and ii>=0):
    print(i, ii, iii)
    sys.exit()
    
print(-1,-1,-1)

Measured memory_bytes: 12484
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

#define ll long long

using namespace std;
 
int main(){

    int n,k;
    vector<int> h;
    cin >> n >> k;

    for(int i = 0; i < n; i++){
        int hi;
        cin >> hi;
        h.push_back(hi);
    }

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

    int tmp = INT_MAX;

    for(int i = 0; i + k - 1 < n; i++){
        tmp = min(tmp, h[i + k - 1] - h[i]);
    }

    cout << tmp << endl;
 
    return 0;
}

Measured memory_bytes: 892
#include<bits/stdc++.h>
using namespace std;
const int N =1e4+100;

int main()
{
    int n;
    char s[N];

    while(~scanf("%d%s",&n,s))
    {
        for(int i=0;s[i]!='\0';i++)
        {
            s[i] =((s[i]-'A')+n)%26+'A';
        }
        printf("%s\n",s);
    }
    return 0;
}


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

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

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

int main() {
    int a[1000], n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    trace(a, n);
    insertionSort(a, n);
}

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

int main()
{
	string S, T;
	cin >> S >> T;

	if (T.length() - S.length() != 1) {
		cout << "No" << endl;
		return 0;
	}

	for (int i = 0; i < S.length(); i++) {
		if (S[i] != T[i]) {
			cout << "No" << endl;
			return 0;
		}
	}

	cout << "Yes" << endl;
}





Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
int main(){
  int H,W;
  cin>>H>>W;
  vector<vector<char>> board(H,vector<char>(W));
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cin>>board.at(i).at(j);
    }
  }
  for(int i=0;i<H+2;i++){
    for(int j=0;j<W+2;j++){
      if(i==0 || i==H+1){
        cout<<'#';
      }
      else if(i>=1 && i<=H && (j==0 || j==W+1)){
        cout<<'#';
      }
      else{
        cout<<board.at(i-1).at(j-1);
      }
      if(j==W+1){
        cout<<endl;
      }
    }
  }
  return 0;
}

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

int main() {
    long long a, b, x;
    cin >> a >> b >> x;

    if(a == 0 && b == 0) {
        cout << 1;
    }
    else if(a == 0 && 0 < b) {
        cout << b/x + 1;
    }
    else {
        cout << b/x - (a-1)/x;
    }
    
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <numeric>
#include <iomanip>
#include <set>
#include <string.h>

using namespace std;

typedef long long ll;

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REP3(i,st,en) for(ll (i)=(st);(i)<(en);(i)++)

using P = pair<ll, ll>;
const int MOD = 1e9+7;
const ll INF = 1e+14;
const double PI = 3.14159265349;


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

  ll N, x;
  cin >> N >> x;
  vector<ll> a(N);
  ll ans = 0;
  REP(i,N){
    cin >> a[i];
    if (a[i]>x){
      ans += a[i] - x;
      a[i] = x;
    }
  }

  REP(i,N-1){
    if (a[i]+a[i+1]>x){
      ans += a[i]+a[i+1]-x;
      a[i+1] -= a[i]+a[i+1]-x;
    }
  }

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


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;
using ll = long long;
using pll = pair<ll, ll>;
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#define VREP(s, ite) for (auto ite = s.begin(); ite != s.end(); ++ite)
#define FI first
#define SE second
//#define endl "\n"
#define ciosup  \
    cin.tie(0); \
    ios::sync_with_stdio(false);
#define eb emplace_back
#define vint vector<int>
constexpr ll INF = 1e9 + 7;
constexpr ll MOD = 998244353;

ll dp[310][300 * 300 + 1000];
ll dp2[310][300 * 300 + 1000];

ll my_pow(ll x, int n){
    ll y = 1;
    while(n != 0){
        if (n & 1) y= y*x % MOD;
        x = x * x % MOD;
        n >>= 1;
    }
    return y;
}

int main()
{
    ciosup;
    int n;
    cin >> n;
    vint a(n);
    ll tot = 0;
    REP(i, n)
    {
        cin >> a[i];
        tot += a[i];
    }
    dp[0][0] = 1;
    REP(i,n){
        REP(j,tot+1){
            dp[i + 1][j + a[i]] = (dp[i + 1][j + a[i]] + dp[i][j]) % MOD;
            dp[i + 1][j] = (dp[i + 1][j] + 2*dp[i][j] % MOD) % MOD;
        }
    }
    dp2[0][0] = 1;
    REP(i, n)
    {
        REP(j, tot + 1)
        {
            dp2[i + 1][j + a[i]] = (dp2[i + 1][j + a[i]] + dp2[i][j]) % MOD;
            dp2[i + 1][j] = (dp2[i + 1][j] + dp2[i][j]) % MOD;
        }
    }
    ll ans = my_pow(3, n);
    ll sub = 0;
    FOR(i, tot / 2 + tot % 2, tot + 1)
    {
        sub = (sub + dp[n][i]) % MOD;
    }
    if (tot % 2 == 0)
        sub = (sub + MOD - dp2[n][tot / 2] % MOD) % MOD;

    ans = (ans + MOD - 3*sub % MOD) % MOD;
    cout << ans << endl;
}

Measured memory_bytes: 431616
#!/usr/bin/python3
# -*- coding: utf-8 -*-


"""
https://beta.atcoder.jp/contests/abc054/tasks/abc54_c
"""

import sys
import math
import copy
from inspect import currentframe

def debug_print(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args), file=sys.stderr)

N, M = map(int, input().split())
graph = [[] for _ in range(N)]

for _ in range(M):
    a, b  = map(int, input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
    
# 普通にdfsで行けるイメージなのでそれをする
# パスの数を返す
def dfs(node, visited_list):
    paths = 0
    visited = copy.copy(visited_list)
    if node not in visited:
        visited.append(node)
    debug_print(node)
    debug_print(visited_list)
    if len(visited) == N:
        return 1
    for to in graph[node]:
        if to not in visited:
            paths += dfs(to, visited)
    return paths
        
print(dfs(0, [0]))
        


                                                                                                        


Measured memory_bytes: 4748
#include<bits/stdc++.h>
#define rep(i,n,m) for(int i = (n); i <(m); i++)
#define rrep(i,n,m) for(int i = (n) - 1; i >=(m); i--)
using namespace std;
using ll = long long;
const ll INF = 1000000000000000000;
int main()
{
    int n;
    cin >> n;
    vector<ll> csum(n+1, 0);
    rep(i, 0, n)
    {
        cin >> csum[i+1];
        csum[i+1] += csum[i];
    }

    ll res = INF;
    rep(i, 0, n)
    {
        ll left = csum[i+1];
        ll right = csum[n] - csum[i+1];
        res = min(res, abs(right-left));
        // cout << left << ' ' << right << endl;
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 1792
import java.io.PrintWriter
import kotlin.math.min

fun next() = readLine()!!
fun nextInt() = next().toInt()
fun nextLong() = next().toLong()
fun nextDouble() = next().toDouble()
fun nextList() = next().split(" ")
fun nextIntList() = nextList().map(String::toInt)
fun nextLongList() = nextList().map(String::toLong)
fun nextDoubleList() = nextList().map(String::toDouble)

val pw = PrintWriter(System.out)
fun print(s: Any = "") = pw.print(s)
fun println(s: Any = "") = pw.println(s)

fun <T> Iterable<T>.join(separator: CharSequence = ", ", prefix: CharSequence = "", postfix: CharSequence = "") = joinToString(separator, prefix, postfix)
fun <T> Array<T>.join(separator: CharSequence = ", ", prefix: CharSequence = "", postfix: CharSequence = "") = joinToString(separator, prefix, postfix)

fun main(args: Array<String>) {
    main()
    pw.flush()
}

fun main() {
    val (X, Y) = nextIntList()
    if ((X + Y) % 3 != 0) {
        println(0)
        return
    }
    val n = (X + Y) / 3
    val k = min(X, Y) - n
    val C = Combination2(n)
    val ans = C(n, k)
    println(ans)
}

class Combination2(n: Int) {
    private val fact = Array<MInt?>(n + 1) { null }

    init {
        fact[0] = MInt(1)
        (1..n).forEach { i -> fact[i] = fact[i - 1]!! * MInt(i) }
    }

    operator fun invoke(n: Int, k: Int): MInt {
        if (k < 0 || n < k) return MInt(0)
        return (fact[n]!! / (fact[k]!! * fact[n - k]!!))
    }
}

class MInt {
    private val MOD = 1000000007L
    var v: Long

    constructor(v: Long) {
        this.v = v % MOD
    }

    constructor(v: Int) {
        this.v = v.toLong() % MOD
    }

    operator fun plus(b: MInt): MInt {
        val a = MInt(v)
        a.v += b.v
        if (a.v >= MOD) a.v -= MOD
        return a
    }

    operator fun plus(b: Int) = plus(MInt(b))
    operator fun plus(b: Long) = plus(MInt(b))

    operator fun minus(b: MInt): MInt {
        val a = MInt(v)
        a.v -= b.v
        if (a.v < 0) a.v += MOD
        return a
    }

    operator fun minus(b: Int) = minus(MInt(b))
    operator fun minus(b: Long) = minus(MInt(b))

    operator fun times(b: MInt): MInt {
        val a = MInt(v)
        a.v *= b.v
        a.v %= MOD
        return a
    }

    operator fun div(b: MInt): MInt {
        return MInt(v) * b.inv()
    }

    fun inv(): MInt {
        var a = v
        var b = MOD
        var u = 1L
        var w = 0L
        while (b != 0L) {
            val t = a / b
            a -= t * b
            u -= t * w
            var tmp = a
            a = b
            b = tmp
            tmp = u
            u = w
            w = tmp
        }
        u %= MOD
        if (u < 0) u += MOD
        return MInt(u)
    }

    fun pow(N: Int) = pow(N.toLong())

    fun pow(N: Long): MInt {
        var ans = MInt(1)
        var a = this
        var n = N
        while (n > 0) {
            if (n.and(1) == 1L) {
                ans *= a
            }
            a *= a
            n = n.shr(1)
        }
        return ans
    }

    override fun toString(): String {
        return v.toString()
    }
}


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

struct BM {
  int V;
  vector<vector<int > > G;
  vector<int> match;
  vector<bool> used;
  BM(int n=0) : V(n), G(n), match(n, -1), used(n) {}
  inline void add(int u, int v) {
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }
  bool dfs(int v) {
    used[v] = true;
    for(int u:G[v]) {
      int w = match[u];
      if(w < 0 or (!used[w] and dfs(w))) {
        match[v] = u;
        match[u] = v;
        return true;
      }
    }
    return false;
  }
  int bipartite_matching() {
    int res = 0;
    rep(v, V) {
      if(match[v] < 0) {
        rep(i, v) used[i] = 0;
        if(dfs(v)) res++;
      }
    }
    return res;
  }
};

const int N = 100;

//head

int n;
int a[N], b[N], c[N], d[N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  BM bpm(n<<1);
  rep(i, n) cin >> a[i] >> b[i];
  rep(i, n) cin >> c[i] >> d[i];
  rep(i, n) rep(j, n) if(a[i] < c[j] and b[i] < d[j]) {
    bpm.add(i, j+n);
  }
  cout << bpm.bipartite_matching() << endl;
}

Measured memory_bytes: 3636