K11720 Milk Measurement-B[USACO-2017-Dec-B]c++代码

以下是题目和代码：

题目描述：

农夫约翰想要了解他的奶牛们每天产生的牛奶量。他有 $N$ 头奶牛，编号为 $1,2,…,N$，他想要在连续的 $M$ 天里知道这些奶牛的总产量。他记录了每头奶牛在这 $M$ 天里每天产生的牛奶数量。

每天的奶牛产量都是非负的，但不一定相同。约翰想要知道哪些奶牛在这 $M$ 天里总共产生了至少 $G$ 加仑的牛奶。请帮助约翰找出这些奶牛。由于总共有 $N$ 头奶牛，你的算法的时间复杂度至多为 $O(NM)$，否则你可能会超时。

输入格式

第一行包含三个整数 $N,G,M$。

接下来 $N$ 行，每行包含 $M$ 个整数，表示每头奶牛在这 $M$ 天里每天的产量。

输出格式

每行输出一个奶牛的编号，表示这些奶牛中的每一头最少产出了 $G$ 加仑的牛奶。

输出这些编号的顺序应该与它们在输入中出现的顺序相同。

如果没有奶牛的总产量至少为 $G$ 加仑，则输出 NONE。

数据范围

$1≤N,M≤1000$

$0≤G≤10^9$

输入样例：

5 24 2
15 20
20 10
25 18
30 32
40 50

输出样例：

1
2
3
4

c++ 代码：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1010;

int n, g, m;
int sum[N][N]; //记录前缀和
vector<int> ans;

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

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
        {
            int x;
            cin >> x;
            sum[i][j] = sum[i][j - 1] + x;
        }

    for (int i = 1; i <= n; ++i)
    {
        int s = 0;
        for (int j = 1; j <= m; ++j)
            s += sum[i][min(j + m - 1, m)] - sum[i][j - 1];

        if (s >= g * m) ans.push_back(i);
    }

    if (ans.empty()) puts("NONE");
    else
        for (auto x : ans) cout << x << endl;

    return 0;
}